<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">

<script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
<link href="//cdn.bootcss.com/pace/1.0.2/themes/pink/pace-theme-flash.css" rel="stylesheet">
<meta name="theme-color" content="#fff">
<meta name="generator" content="Hexo 5.4.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.ico">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#fff">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="https://fonts.cat.net/css?family=Lato:300,300italic,400,400italic,700,700italic%7CRoboto+Slab:300,300italic,400,400italic,700,700italic%7CDejaVu+Sans+Mono:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.3/css/all.min.css" integrity="sha256-2H3fkXt6FEmrReK448mDVGKb3WW2ZZw35gI7vqHOE4Y=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.css" integrity="sha256-no0c5ccDODBwp+9hSmV5VvPpKwHCpbVzXHexIkupM6U=" crossorigin="anonymous">
  <script src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.js" integrity="sha256-a5YRB27CcBwBFcT5EF/f3E4vzIqyHrSR878nseNYw64=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"hyw-zero.github.io","root":"/","images":"/images","scheme":"Gemini","version":"8.7.0","exturl":false,"sidebar":{"position":"left","display":"hide","padding":10,"offset":12,"scrollpercent":false,"onmobile":false},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>
<meta name="description" content="1.丑数1.1 题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。">
<meta property="og:type" content="article">
<meta property="og:title" content="剑指offer算法练习">
<meta property="og:url" content="https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/index.html">
<meta property="og:site_name" content="ZERO">
<meta property="og:description" content="1.丑数1.1 题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-04T21:02:30.000Z">
<meta property="article:modified_time" content="2021-08-22T11:17:57.557Z">
<meta property="article:author" content="hyw-zero">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/","path":"2020/10/05/剑指offer算法练习/","title":"剑指offer算法练习"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>剑指offer算法练习 | ZERO</title>
  



<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="ZERO" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>
  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">ZERO</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">keep  learning, be  curious !</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-%E4%B8%91%E6%95%B0"><span class="nav-text">1.丑数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">1.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">1.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">1.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">1.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-%E5%B7%A6%E7%A7%BB%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-text">2.左移旋转字符串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#2-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">2.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">2.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">2.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">2.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%85%AC%E5%85%B1%E7%BB%93%E7%82%B9"><span class="nav-text">3.两个链表的第一个公共结点</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">3.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">3.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">3.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#4-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F"><span class="nav-text">4.二叉树的镜像</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#4-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">4.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-2-%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0"><span class="nav-text">4.2 输入描述:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-3-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">4.3 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-4-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">4.4 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-5-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">4.5 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5-%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9F%A5%E6%89%BE"><span class="nav-text">5.二维数组中的查找</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">5.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">5.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">5.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">5.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#6-%E5%B7%A6%E7%A7%BB%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-text">6.左移旋转字符串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#6-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">6.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">6.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">6.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">6.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#8-%E5%8C%85%E5%90%ABmin%E5%87%BD%E6%95%B0%E7%9A%84%E6%A0%88"><span class="nav-text">8.包含min函数的栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#8-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">8.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#8-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">8.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#8-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">8.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#9-%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97"><span class="nav-text">9.斐波那契数列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#9-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">9.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">9.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">9.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">9.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#10-%E8%B7%B3%E5%8F%B0%E9%98%B6"><span class="nav-text">10.跳台阶</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#10-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">10.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#10-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">10.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#10-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">10.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#10-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">10.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#11-%E5%8F%98%E6%80%81%E8%B7%B3%E5%8F%B0%E9%98%B6"><span class="nav-text">11.变态跳台阶</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#11-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">11.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#11-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">11.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#11-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">11.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#11-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">11.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#12-%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8"><span class="nav-text">12.合并两个排序链表</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#12-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">12.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#12-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">12.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#12-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">12.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#12-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">12.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#13-%E5%92%8C%E4%B8%BAS%E7%9A%84%E4%B8%A4%E4%B8%AA%E6%95%B0%E5%AD%97"><span class="nav-text">13.和为S的两个数字</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#13-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">13.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#13-2-%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0"><span class="nav-text">13.2 输出描述:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#13-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">13.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#14-%E5%92%8C%E4%B8%BAS%E7%9A%84%E8%BF%9E%E7%BB%AD%E6%AD%A3%E6%95%B0%E5%BA%8F%E5%88%97"><span class="nav-text">14.和为S的连续正数序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#14-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">14.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-2-%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0"><span class="nav-text">14.2 输出描述:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">14.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">14.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#15-%E6%8A%8A%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%BD%AC%E6%88%90%E6%95%B4%E6%95%B0"><span class="nav-text">15.把字符串转成整数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#15-1%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">15.1题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#14-%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E5%AD%97"><span class="nav-text">14.数组中出现超过一半的数字</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#14-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0-1"><span class="nav-text">14.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-2-%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0-1"><span class="nav-text">14.2 输出描述:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-3-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">14.3 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-4-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">14.4 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-5-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">14.5 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#15-%E5%B7%A6%E7%A7%BB%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-text">15.左移旋转字符串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#15-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">15.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#15-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">15.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#15-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">15.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#15-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">15.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#16-%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-text">16.平衡二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#16-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">16.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#16-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">16.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#16-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">16.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#17-%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8%E7%9A%84%E5%85%A5%E5%8F%A3%E8%8A%82%E7%82%B9"><span class="nav-text">17.循环链表的入口节点</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#17-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">17.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#17-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">17.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#17-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">17.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#17-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">17.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#18-%E6%89%91%E5%85%8B%E7%89%8C%E9%A1%BA%E5%AD%90"><span class="nav-text">18.扑克牌顺子</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#18-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">18.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#18-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">18.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#18-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">18.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#18-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">18.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#19-%E6%95%B0%E5%80%BC%E7%9A%84%E6%95%B4%E6%95%B0%E6%AC%A1%E6%96%B9"><span class="nav-text">19.数值的整数次方</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#19-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">19.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#19-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">19.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#19-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">19.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#19-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">19.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#20-%E6%95%B0%E5%AD%97%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0"><span class="nav-text">20.数字在排序数组中出现的次数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#20-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">20.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#20-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">20.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#20-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">20.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#21-%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E5%AD%97"><span class="nav-text">21.数组中出现超过一半的数字</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#21-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">21.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#21-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">21.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#21-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">21.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#21-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">21.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#22-%E6%95%B0%E7%BB%84%E4%B8%AD%E5%87%BA%E7%8E%B0%E8%B6%85%E8%BF%87%E4%B8%80%E5%8D%8A%E7%9A%84%E6%95%B0%E5%AD%97"><span class="nav-text">22.数组中出现超过一半的数字</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#22-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">22.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#22-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">22.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#22-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">22.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#22-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">22.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#23-%E5%92%8C%E4%B8%BAS%E7%9A%84%E8%BF%9E%E7%BB%AD%E6%AD%A3%E6%95%B0%E5%BA%8F%E5%88%97"><span class="nav-text">23.和为S的连续正数序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#23-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">23.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#23-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">23.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#23-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">23.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#24-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9"><span class="nav-text">24.数组中的逆序对</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#24-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">24.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#24-2-%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0"><span class="nav-text">24.2 输入描述:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#24-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">24.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#25-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E6%95%B0%E5%AD%97"><span class="nav-text">25.数组中的重复数字</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#25-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">25.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#25-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%8F%8A%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">25.2 解题思路及代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#26-%E6%95%B4%E6%95%B0%E4%B8%AD1%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0"><span class="nav-text">26.整数中1出现的次数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#26-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">26.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#26-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">26.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#26-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">26.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#26-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">26.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#27-%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC"><span class="nav-text">27.旋转数组的最小值</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#27-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">27.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#27-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">27.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#27-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">27.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#27-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">27.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#28-%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0"><span class="nav-text">28.最小的K个数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#28-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">28.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#28-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">28.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#28-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">28.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#28-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">28.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#29-%E6%A0%88%E7%9A%84%E5%8E%8B%E5%85%A5%EF%BC%8C%E5%BC%B9%E5%87%BA%E5%BA%8F%E5%88%97"><span class="nav-text">29.栈的压入，弹出序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#29-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">29.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#29-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">29.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#29-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">29.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#29-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">29.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#30-%E6%B1%821-2-3-%E2%80%A6-n"><span class="nav-text">30.求1+2+3+…+n</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#30-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">30.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#30-2%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%EF%BC%9A"><span class="nav-text">30.2解题思路：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#30-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">30.3 C++代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#31-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6"><span class="nav-text">31.二叉树的深度</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#31-1%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">31. 1题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#31-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">31.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#31-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">31.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#32-%E6%8A%8A%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%BD%AC%E6%88%90%E6%95%B4%E6%95%B0"><span class="nav-text">32.把字符串转成整数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#32-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">32.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#32-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">32.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#32-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">32.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#33-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC"><span class="nav-text">33.滑动窗口最大值</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#33-1-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">33.1 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#33-2-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">33.2 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#33-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">33.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#34-%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E5%8A%A8%E6%80%81%E5%92%8C"><span class="nav-text">34.连续子数组的动态和</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#34-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">34.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#34-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">34.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#34-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">34.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#34-5-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">34.5 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#35-%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC"><span class="nav-text">35.替换空格</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#35-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">35.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#35-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">35.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#35-3-c-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">35.3 c++代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#36-%E7%BF%BB%E8%BD%AC%E5%8D%95%E8%AF%8D%E9%A1%BA%E5%BA%8F%E5%88%97"><span class="nav-text">36.翻转单词顺序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#36-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">36.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#36-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">36.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#36-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">36.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#36-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">36.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#37-%E8%B0%83%E6%95%B4%E6%95%B0%E7%BB%84%E5%A5%87%E6%95%B0%E4%BD%8D%E4%BA%8E%E5%81%B6%E6%95%B0%E5%89%8D%E9%9D%A2"><span class="nav-text">37.调整数组奇数位于偶数前面</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#37-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">37.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#37-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">37.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#37-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">37.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#37-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">37.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#38-%E8%BF%9B%E5%88%B6%E4%B8%AD1%E7%9A%84%E4%B8%AA%E6%95%B0"><span class="nav-text">38.进制中1的个数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#38-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">38.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#38-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">38.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#38-3-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">38.3 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#39-%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E5%8A%A8%E6%80%81%E5%92%8C"><span class="nav-text">39.连续子数组的动态和</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#39-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">39.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#39-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">39.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#39-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">39.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#39-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">39.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#40-%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-text">40.重建二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#40-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">40.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#40-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">40.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#40-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">40.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#40-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">40.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#41-%E9%93%BE%E8%A1%A8%E4%B8%AD%E5%80%92%E6%95%B0%E7%AC%ACK%E4%B8%AA%E8%8A%82%E7%82%B9"><span class="nav-text">41.链表中倒数第K个节点</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#41-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">41. 1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#41-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">41.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#41-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">41.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#41-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">41.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#42-%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8"><span class="nav-text">42.反转链表</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#42-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">42.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#42-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">42.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#42-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">42.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#42-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">42.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#43-%E9%A1%BA%E6%97%B6%E9%92%88%E6%89%93%E5%8D%B0%E7%9F%A9%E9%98%B5"><span class="nav-text">43.顺时针打印矩阵</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#43-1-%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0"><span class="nav-text">43.1 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#43-2-%E9%A2%98%E7%9B%AE%E7%BF%BB%E8%AF%91"><span class="nav-text">43.2 题目翻译</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#43-3-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF"><span class="nav-text">43.3 解题思路</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#43-4-C-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">43.4 C++ 代码实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#44-%E5%B7%B2%E7%9F%A5%E5%90%8E%E5%BA%8F%E5%92%8C%E4%B8%AD%E5%BA%8F%EF%BC%8C%E6%B1%82%E6%A0%91"><span class="nav-text">44 已知后序和中序，求树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#44-1-c-%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-text">44.1 c++代码实现</span></a></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
            <div class="site-overview">
              <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="hyw-zero"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">hyw-zero</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">13</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">5</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="mailto:hyw33666@gmail.com" title="E-Mail → mailto:hyw33666@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://github.com/hyw-zero" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;hyw-zero" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
  </div>


  <div class="links-of-blogroll site-overview-item animated">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      推荐阅读
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="http://c.biancheng.net/cplus/" title="http:&#x2F;&#x2F;c.biancheng.net&#x2F;cplus&#x2F;" rel="noopener" target="_blank">c语言中文网</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://github.com/chenshuo/documents/downloads" title="https:&#x2F;&#x2F;github.com&#x2F;chenshuo&#x2F;documents&#x2F;downloads" rel="noopener" target="_blank">Linux多线程服务端</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://github.com/SilverMaple/STLSourceCodeNote" title="https:&#x2F;&#x2F;github.com&#x2F;SilverMaple&#x2F;STLSourceCodeNote" rel="noopener" target="_blank">STL源码剖析</a>
        </li>
    </ul>
  </div>
<div class="cc-license animated" itemprop="sponsor">
  <a href="https://www.netlify.com" class="cc-opacity" title="Deploy with Netlify → https://www.netlify.com" target="_blank"><img width="80" src="https://www.netlify.com/img/global/badges/netlify-dark.svg" alt="Netlify"></a>
</div>
            </div>
        </div>
	    </div>
	  

    </div>
	<iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=280 height=300 src="//music.163.com/outchain/player?type=0&id=411680085&auto=1&height=430"></iframe>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="hyw-zero">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="ZERO">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          剑指offer算法练习
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-04 21:02:30" itemprop="dateCreated datePublished" datetime="2020-10-04T21:02:30Z">2020-10-04</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%89%91%E6%8C%87offer/" itemprop="url" rel="index"><span itemprop="name">剑指offer</span></a>
        </span>
    </span>

  
    <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span id="busuanzi_value_page_pv"></span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="1-丑数"><a href="#1-丑数" class="headerlink" title="1.丑数"></a>1.丑数</h2><h3 id="1-1-题目描述"><a href="#1-1-题目描述" class="headerlink" title="1.1 题目描述"></a>1.1 题目描述</h3><p>把只包含质因子2、3和5的数称作丑数（Ugly Number）。 <span id="more"></span> 例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。</p>
<h3 id="1-2-题目翻译"><a href="#1-2-题目翻译" class="headerlink" title="1.2 题目翻译"></a>1.2 <strong>题目翻译</strong></h3><p>按顺序添加丑数</p>
<h3 id="1-3-解题思路"><a href="#1-3-解题思路" class="headerlink" title="1.3 解题思路"></a>1.3 解题思路</h3><p>丑数能够分解成<br>$$<br>2^x<em>3^y</em>5^z,<br>$$<br>所以只需要把得到的丑数不断地乘以2、3、5之后并放入他们应该放置的位置即可，<br>而此题的难点就在于如何有序的放在合适的位置。<br>1乘以 （2、3、5）=2、3、5；<br>2乘以（2、3、5）=4、6、10；<br>3乘以（2、3、5）=6,9,15；<br>5乘以（2、3、5）=10、15、25；<br>从这里我们可以看到如果不加策略地添加丑数是会有重复并且无序，<br>而在2x， 3y， 5z中，如果x=y=z那么最小丑数一定是乘以2的，但关键是有可能存在x》y》z的情况，所以我们要维持三个指针来记录当前乘以2、乘以3、乘以5的最小值，然后当其被选为新的最小值后，要把相应的指针+1；因为这个指针会逐渐遍历整个数组，因此最终数组中的每一个值都会被乘以2、乘以3、乘以5，也就是实现了我们最开始的想法，只不过不是同时成乘以2、3、5，而是在需要的时候乘以2、3、5.</p>
<h3 id="1-4-C-代码实现"><a href="#1-4-C-代码实现" class="headerlink" title="1.4 C++ 代码实现"></a>1.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">GetUglyNumber_Solution</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (index &lt; <span class="number">7</span>)<span class="keyword">return</span> index;</span><br><span class="line">		<span class="keyword">int</span> p2 = <span class="number">0</span>, p3 = <span class="number">0</span>, p5 = <span class="number">0</span>;<span class="comment">//初始化三个指向三个潜在成为最小丑数的位置</span></span><br><span class="line">		<span class="keyword">int</span>* ret = <span class="keyword">new</span> <span class="keyword">int</span>[index];</span><br><span class="line">		ret[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">int</span> temp;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; index; ++i) &#123;</span><br><span class="line">			temp = <span class="built_in">min</span>(ret[p2] * <span class="number">2</span>, ret[p3] * <span class="number">3</span>);</span><br><span class="line">			ret[i] = <span class="built_in">min</span>(temp, ret[p5] * <span class="number">5</span>);</span><br><span class="line">			<span class="keyword">if</span> (ret[i] == ret[p2] * <span class="number">2</span>)p2++;<span class="comment">//为了防止重复需要三个if都能够走到</span></span><br><span class="line">			<span class="keyword">if</span> (ret[i] == ret[p3] * <span class="number">3</span>)p3++;<span class="comment">//为了防止重复需要三个if都能够走到</span></span><br><span class="line">			<span class="keyword">if</span> (ret[i] == ret[p5] * <span class="number">5</span>)p5++;<span class="comment">//为了防止重复需要三个if都能够走到</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> ret[index - <span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="2-左移旋转字符串"><a href="#2-左移旋转字符串" class="headerlink" title="2.左移旋转字符串"></a>2.左移旋转字符串</h2><h3 id="2-1-题目描述"><a href="#2-1-题目描述" class="headerlink" title="2.1 题目描述"></a>2.1 题目描述</h3><p>用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。</p>
<h3 id="2-2-题目翻译"><a href="#2-2-题目翻译" class="headerlink" title="2.2 题目翻译"></a>2.2 题目翻译</h3><p>栈：先进后出     队列：先进先出</p>
<h3 id="2-3-解题思路"><a href="#2-3-解题思路" class="headerlink" title="2.3 解题思路"></a>2.3 解题思路</h3><p>一个栈进行入队操作，一个进行出队操作。</p>
<h3 id="2-4-C-代码实现"><a href="#2-4-C-代码实现" class="headerlink" title="2.4 C++ 代码实现"></a>2.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>-&gt;stack1.<span class="built_in">push</span>(node);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> ret ;</span><br><span class="line">        <span class="keyword">if</span>(<span class="keyword">this</span>-&gt;stack2.<span class="built_in">empty</span>())&#123;</span><br><span class="line">            <span class="keyword">while</span>(!<span class="keyword">this</span>-&gt;stack1.<span class="built_in">empty</span>())&#123;</span><br><span class="line">                <span class="keyword">this</span>-&gt;stack2.<span class="built_in">push</span>(<span class="keyword">this</span>-&gt;stack1.<span class="built_in">top</span>());</span><br><span class="line">                <span class="keyword">this</span>-&gt;stack1.<span class="built_in">pop</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        ret = <span class="keyword">this</span>-&gt;stack2.<span class="built_in">top</span>();</span><br><span class="line">        <span class="keyword">this</span>-&gt;stack2.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="keyword">return</span> ret;</span><br><span class="line">    &#125;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt; stack1;</span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt; stack2;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="3-两个链表的第一个公共结点"><a href="#3-两个链表的第一个公共结点" class="headerlink" title="3.两个链表的第一个公共结点"></a>3.两个链表的第一个公共结点</h2><h3 id="3-1-题目描述"><a href="#3-1-题目描述" class="headerlink" title="3.1 题目描述"></a>3.1 题目描述</h3><p>输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）</p>
<h3 id="3-2-解题思路"><a href="#3-2-解题思路" class="headerlink" title="3.2 解题思路"></a>3.2 解题思路</h3><p>给定两个单链表<code>A，B</code>，假设一定含有公共结点，返回第一个公共结点的指针。<br>但A，B公共节点前的长度不一定相等。<br>需要使得AB长度一致，双指针加 AB相加链表</p>
<h3 id="3-3-C-代码实现"><a href="#3-3-C-代码实现" class="headerlink" title="3.3 C++ 代码实现"></a>3.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct ListNode *next;</span></span><br><span class="line"><span class="comment">	ListNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">FindFirstCommonNode</span><span class="params">( ListNode* pHead1, ListNode* pHead2)</span> </span>&#123;</span><br><span class="line">      ListNode* p1=pHead1;</span><br><span class="line">      ListNode* p2=pHead2;</span><br><span class="line">        <span class="keyword">while</span>(p1 != p2)&#123;</span><br><span class="line">           p1=p1?p1-&gt;next:pHead2;</span><br><span class="line">           p2=p2?p2-&gt;next:pHead1;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> p1;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">GetNumberOfK</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; nums ,<span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">upper_bound</span>(nums.<span class="built_in">begin</span>(), nums.<span class="built_in">end</span>(), target) - <span class="built_in">lower_bound</span>(nums.<span class="built_in">begin</span>(), nums.<span class="built_in">end</span>(), target);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="4-二叉树的镜像"><a href="#4-二叉树的镜像" class="headerlink" title="4.二叉树的镜像"></a>4.二叉树的镜像</h2><h3 id="4-1-题目描述"><a href="#4-1-题目描述" class="headerlink" title="4.1 题目描述"></a>4.1 题目描述</h3><p>操作给定的二叉树，将其变换为源二叉树的镜像。</p>
<h3 id="4-2-输入描述"><a href="#4-2-输入描述" class="headerlink" title="4.2 输入描述:"></a>4.2 输入描述:</h3><figure class="highlight sh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">二叉树的镜像定义：源二叉树 </span><br><span class="line">    	    8</span><br><span class="line">    	   /  \</span><br><span class="line">    	  6   10</span><br><span class="line">    	 / \  / \</span><br><span class="line">    	5  7 9 11</span><br><span class="line">    	镜像二叉树</span><br><span class="line">    	    8</span><br><span class="line">    	   /  \</span><br><span class="line">    	  10   6</span><br><span class="line">    	 / \  / \</span><br><span class="line">    	11 9 7  5</span><br></pre></td></tr></table></figure>
<h3 id="4-3-题目翻译"><a href="#4-3-题目翻译" class="headerlink" title="4.3 题目翻译"></a>4.3 题目翻译</h3><p>二叉树左右节点翻转<br>二叉树一般用递归处理<br>翻转也可以用栈进行处理，先进后出然后就进行了翻转</p>
<h3 id="4-4-解题思路"><a href="#4-4-解题思路" class="headerlink" title="4.4 解题思路"></a>4.4 解题思路</h3><p>二叉树递归实现左右子树交换</p>
<h3 id="4-5-C-代码实现"><a href="#4-5-C-代码实现" class="headerlink" title="4.5 C++ 代码实现"></a>4.5 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct TreeNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct TreeNode *left;</span></span><br><span class="line"><span class="comment">	struct TreeNode *right;</span></span><br><span class="line"><span class="comment">	TreeNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), left(NULL), right(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Mirror</span><span class="params">(TreeNode *pRoot)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">nullptr</span> == pRoot )<span class="keyword">return</span>;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">nullptr</span> == pRoot-&gt;left &amp;&amp; <span class="literal">nullptr</span> == pRoot-&gt;right)<span class="keyword">return</span>;<span class="comment">//注释掉也行</span></span><br><span class="line">        TreeNode * temp= pRoot-&gt;left;<span class="comment">//节点交换</span></span><br><span class="line">        pRoot-&gt;left=pRoot-&gt;right;</span><br><span class="line">        pRoot-&gt;right=temp;</span><br><span class="line">        <span class="keyword">if</span>(pRoot-&gt;left)&#123;</span><br><span class="line">            <span class="built_in">Mirror</span>(pRoot-&gt;left);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(pRoot-&gt;right)&#123;</span><br><span class="line">            <span class="built_in">Mirror</span>(pRoot-&gt;right);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="5-二维数组中的查找"><a href="#5-二维数组中的查找" class="headerlink" title="5.二维数组中的查找"></a>5.二维数组中的查找</h2><h3 id="5-1-题目描述"><a href="#5-1-题目描述" class="headerlink" title="5.1 题目描述"></a>5.1 题目描述</h3><p>在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。</p>
<h3 id="5-2-题目翻译"><a href="#5-2-题目翻译" class="headerlink" title="5.2 题目翻译"></a>5.2 题目翻译</h3><p>每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。<br>即，每一行最后一个数为该行最大。每一列第一个数为该行最小。</p>
<h3 id="5-3-解题思路"><a href="#5-3-解题思路" class="headerlink" title="5.3 解题思路"></a>5.3 解题思路</h3><p><strong>思路一</strong><br>​    遍历二维数组，进行查找。时间复杂度为O(n^2) （leetcode无法通过）<br><strong>思路二</strong><br>​    右上角比较法。<br>​    target &gt; 右上角   行加1.继续比较<br>​    target&lt; 右上角  列减1，继续比较<br>​    target = 该值 return1；</p>
<h3 id="5-4-C-代码实现"><a href="#5-4-C-代码实现" class="headerlink" title="5.4 C++ 代码实现"></a>5.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">Find</span><span class="params">(<span class="keyword">int</span> target, vector&lt;vector&lt;<span class="keyword">int</span>&gt; &gt; array)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(array.<span class="built_in">empty</span>())<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> x= array[<span class="number">0</span>].<span class="built_in">size</span>(); <span class="comment">//列</span></span><br><span class="line">        <span class="keyword">int</span> y= array.<span class="built_in">size</span>();    <span class="comment">//行</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;y;i++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=x<span class="number">-1</span>;j&gt;=<span class="number">0</span>;j--)&#123;</span><br><span class="line">                <span class="keyword">if</span>(target&gt;array[i][j])&#123;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span> <span class="keyword">if</span>(target == array[i][j])&#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="6-左移旋转字符串"><a href="#6-左移旋转字符串" class="headerlink" title="6.左移旋转字符串"></a>6.左移旋转字符串</h2><h3 id="6-1-题目描述"><a href="#6-1-题目描述" class="headerlink" title="6.1 题目描述"></a>6.1 题目描述</h3><p>输入一个链表，按链表从尾到头的顺序返回一个ArrayList；</p>
<h3 id="6-2-题目翻译"><a href="#6-2-题目翻译" class="headerlink" title="6.2 题目翻译"></a>6.2 题目翻译</h3><p>取链表元素，并生成翻转数组。</p>
<h3 id="6-3-解题思路"><a href="#6-3-解题思路" class="headerlink" title="6.3 解题思路"></a>6.3 解题思路</h3><p>思路一</p>
<p>1.递归链表，直到链表next == NULL；插入val;</p>
<p>思路二</p>
<p>1.建立一个栈，遍历链表压栈</p>
<p>2.遍历栈，进行出栈。栈元素插入数组。</p>
<h3 id="6-4-C-代码实现"><a href="#6-4-C-代码实现" class="headerlink" title="6.4 C++ 代码实现"></a>6.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">*  struct ListNode &#123;</span></span><br><span class="line"><span class="comment">*        int val;</span></span><br><span class="line"><span class="comment">*        struct ListNode *next;</span></span><br><span class="line"><span class="comment">*        ListNode(int x) :</span></span><br><span class="line"><span class="comment">*              val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">*        &#125;</span></span><br><span class="line"><span class="comment">*  &#125;;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">printListFromTailToHead</span><span class="params">(ListNode* head)</span> </span>&#123;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt;arr;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> == head )<span class="keyword">return</span> arr;</span><br><span class="line">        stack&lt;<span class="keyword">int</span>&gt;stk;</span><br><span class="line">        ListNode * p = head;</span><br><span class="line">        <span class="keyword">while</span>(<span class="literal">NULL</span> != p)&#123;</span><br><span class="line">            stk.<span class="built_in">push</span>(p-&gt;val);</span><br><span class="line">            p=p-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(!stk.<span class="built_in">empty</span>())&#123;</span><br><span class="line">            arr.<span class="built_in">push_back</span>(stk.<span class="built_in">top</span>());</span><br><span class="line">            stk.<span class="built_in">pop</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p><strong>递归</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">*  struct ListNode &#123;</span></span><br><span class="line"><span class="comment">*        int val;</span></span><br><span class="line"><span class="comment">*        struct ListNode *next;</span></span><br><span class="line"><span class="comment">*        ListNode(int x) :</span></span><br><span class="line"><span class="comment">*              val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">*        &#125;</span></span><br><span class="line"><span class="comment">*  &#125;;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt; arr;<span class="comment">//全局变量</span></span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">printListFromTailToHead</span><span class="params">(ListNode* head)</span> </span>&#123;</span><br><span class="line">        ListNode * p = <span class="literal">NULL</span>;</span><br><span class="line">        p=head;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> != p)&#123;</span><br><span class="line">            <span class="keyword">if</span>(<span class="literal">NULL</span> != p-&gt;next)&#123;</span><br><span class="line">                <span class="built_in">printListFromTailToHead</span>(p-&gt;next);</span><br><span class="line">            &#125;</span><br><span class="line">            arr.<span class="built_in">push_back</span>(p-&gt;val);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="8-包含min函数的栈"><a href="#8-包含min函数的栈" class="headerlink" title="8.包含min函数的栈"></a>8.包含min函数的栈</h2><h3 id="8-1-题目描述"><a href="#8-1-题目描述" class="headerlink" title="8.1 题目描述"></a>8.1 题目描述</h3><p>定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。<br><strong>题目翻译</strong><br>栈加个求最小值的功能</p>
<h3 id="8-2-解题思路"><a href="#8-2-解题思路" class="headerlink" title="8.2 解题思路"></a>8.2 解题思路</h3><p>两个栈，一个放数据，一个放当前最小值。</p>
<h3 id="8-3-C-代码实现"><a href="#8-3-C-代码实现" class="headerlink" title="8.3 C++ 代码实现"></a>8.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        stk.<span class="built_in">push</span>(value);</span><br><span class="line">        <span class="keyword">if</span>(stkm.<span class="built_in">empty</span>())&#123;</span><br><span class="line">            stkm.<span class="built_in">push</span>(value);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">if</span>(value &lt; stkm.<span class="built_in">top</span>())&#123;</span><br><span class="line">                stkm.<span class="built_in">push</span>(value);</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                stkm.<span class="built_in">push</span>(stkm.<span class="built_in">top</span>());</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stk.<span class="built_in">pop</span>();</span><br><span class="line">        stkm.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> stk.<span class="built_in">top</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">min</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> stkm.<span class="built_in">top</span>();</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt; stk;</span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt; stkm;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="9-斐波那契数列"><a href="#9-斐波那契数列" class="headerlink" title="9.斐波那契数列"></a>9.斐波那契数列</h2><h3 id="9-1-题目描述"><a href="#9-1-题目描述" class="headerlink" title="9.1 题目描述"></a>9.1 题目描述</h3><p>大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。</p>
<h3 id="9-2-题目翻译"><a href="#9-2-题目翻译" class="headerlink" title="9.2 题目翻译"></a>9.2 <strong>题目翻译</strong></h3><p>f(n)=f(n-1)+f(n-2)</p>
<p>f(1)=1;</p>
<p>f(0)=0</p>
<h3 id="9-3-解题思路"><a href="#9-3-解题思路" class="headerlink" title="9.3 解题思路"></a>9.3 解题思路</h3><p>一，递归调用  O(2^n)  会超时</p>
<p>二，动态规划  用数组模拟 时间复杂度O(n)  不会超时</p>
<h3 id="9-4-C-代码实现"><a href="#9-4-C-代码实现" class="headerlink" title="9.4 C++ 代码实现"></a>9.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">Fibonacci</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123; <span class="comment">//递归思路</span></span><br><span class="line">        <span class="keyword">if</span>(n&lt;=<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> n;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">Fibonacci</span>(n<span class="number">-1</span>)+<span class="built_in">Fibonacci</span>(n<span class="number">-2</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">Fibonacci</span><span class="params">(<span class="keyword">int</span> n)</span><span class="comment">//数组模拟</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span>* arr = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">        arr[<span class="number">0</span>]=<span class="number">1</span>;arr[<span class="number">1</span>]=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">2</span>;i&lt;n;i++)&#123;</span><br><span class="line">            arr[i]=arr[i<span class="number">-1</span>]+arr[i<span class="number">-2</span>];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr[n<span class="number">-1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="10-跳台阶"><a href="#10-跳台阶" class="headerlink" title="10.跳台阶"></a>10.跳台阶</h2><h3 id="10-1-题目描述"><a href="#10-1-题目描述" class="headerlink" title="10.1 题目描述"></a>10.1 题目描述</h3><p>一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。</p>
<h3 id="10-2-题目翻译"><a href="#10-2-题目翻译" class="headerlink" title="10.2 题目翻译"></a>10.2 <strong>题目翻译</strong></h3><p>斐波拉契数列：斐波那契数列：0，1，1，2，3，5，8，13，21，<br>f(n)=f(n-1)+f(n-2)<br>此题  f(1)=1,f(2)=2</p>
<h3 id="10-3-解题思路"><a href="#10-3-解题思路" class="headerlink" title="10.3 解题思路"></a>10.3 解题思路</h3><p>因为青蛙每次只能跳两级，或者一级。青蛙在n级台阶时，一定是从n-1 或者 n-2 上来的。在1级台阶只有一种，二级台阶有两种。3级台阶时，可能是从2级台阶上来的，或者从一级台阶上来的，为f(3)=f(2)+f(1);</p>
<h3 id="10-4-C-代码实现"><a href="#10-4-C-代码实现" class="headerlink" title="10.4 C++ 代码实现"></a>10.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">jumpFloor</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(number == <span class="number">1</span> || number == <span class="number">0</span>)<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">jumpFloor</span>(number<span class="number">-1</span>)+<span class="built_in">jumpFloor</span>(number<span class="number">-2</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="11-变态跳台阶"><a href="#11-变态跳台阶" class="headerlink" title="11.变态跳台阶"></a>11.变态跳台阶</h2><h3 id="11-1-题目描述"><a href="#11-1-题目描述" class="headerlink" title="11.1 题目描述"></a>11.1 题目描述</h3><p>一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。</p>
<h3 id="11-2-题目翻译"><a href="#11-2-题目翻译" class="headerlink" title="11.2 题目翻译"></a>11.2 <strong>题目翻译</strong></h3><p>第n级为</p>
<p>f(n)=f(n-1)+f(n-2)….f(1)+1</p>
<p>f(1)=1;</p>
<h3 id="11-3-解题思路"><a href="#11-3-解题思路" class="headerlink" title="11.3 解题思路"></a>11.3 解题思路</h3><p>f(n)=f(n-1)+f(n-2)….f(1)+1</p>
<p>.</p>
<p>.</p>
<p>f(3)=f(2)+f(1)+1</p>
<p>f(2)=f(1)+1</p>
<p>f(1)=1;</p>
<h3 id="11-4-C-代码实现"><a href="#11-4-C-代码实现" class="headerlink" title="11.4 C++ 代码实现"></a>11.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">jumpFloorII</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">int</span> res =<span class="number">0</span>;</span><br><span class="line">       <span class="keyword">if</span>(n&lt;=<span class="number">1</span>)<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(n&gt;<span class="number">1</span>)&#123;</span><br><span class="line">            res +=<span class="built_in">jumpFloorII</span>(n<span class="number">-1</span>);</span><br><span class="line">            n--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="12-合并两个排序链表"><a href="#12-合并两个排序链表" class="headerlink" title="12.合并两个排序链表"></a>12.合并两个排序链表</h2><h3 id="12-1-题目描述"><a href="#12-1-题目描述" class="headerlink" title="12.1 题目描述"></a>12.1 题目描述</h3><p>输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。</p>
<h3 id="12-2-题目翻译"><a href="#12-2-题目翻译" class="headerlink" title="12.2 题目翻译"></a>12.2 题目翻译</h3><p>两个链表继续按照从小到大归并排序</p>
<h3 id="12-3-解题思路"><a href="#12-3-解题思路" class="headerlink" title="12.3 解题思路"></a>12.3 解题思路</h3><p>归并排序的链表形式</p>
<h3 id="12-4-C-代码实现"><a href="#12-4-C-代码实现" class="headerlink" title="12.4 C++ 代码实现"></a>12.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct ListNode *next;</span></span><br><span class="line"><span class="comment">	ListNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">Merge</span><span class="params">(ListNode* pHead1, ListNode* pHead2)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> == pHead1)<span class="keyword">return</span> pHead2;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> == pHead2)<span class="keyword">return</span> pHead1;</span><br><span class="line">        ListNode * head = <span class="literal">nullptr</span>;</span><br><span class="line">         <span class="keyword">if</span>(pHead1-&gt;val &lt;= pHead2-&gt;val)&#123;</span><br><span class="line">            head=pHead1;</span><br><span class="line">            pHead1=pHead1-&gt;next;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            head=pHead2;</span><br><span class="line">            pHead2=pHead2-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        ListNode * temp = head;</span><br><span class="line">        <span class="keyword">while</span>(<span class="literal">NULL</span> != pHead1 &amp;&amp; <span class="literal">NULL</span> != pHead2 )&#123;</span><br><span class="line">            <span class="keyword">if</span>(pHead1-&gt;val &lt;= pHead2-&gt;val)&#123;</span><br><span class="line">                temp-&gt;next=pHead1;</span><br><span class="line">                pHead1=pHead1-&gt;next;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                temp-&gt;next=pHead2;</span><br><span class="line">                pHead2=pHead2-&gt;next;</span><br><span class="line">            &#125;</span><br><span class="line">            temp=temp-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp-&gt;next = (<span class="literal">NULL</span> == pHead1)?pHead2:pHead1;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="13-和为S的两个数字"><a href="#13-和为S的两个数字" class="headerlink" title="13.和为S的两个数字"></a>13.和为S的两个数字</h2><h3 id="13-1-题目描述"><a href="#13-1-题目描述" class="headerlink" title="13.1 题目描述"></a>13.1 题目描述</h3><p>输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。</p>
<h3 id="13-2-输出描述"><a href="#13-2-输出描述" class="headerlink" title="13.2 输出描述:"></a>13.2 输出描述:</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">对应每个测试案例，输出两个数，小的先输出。</span><br></pre></td></tr></table></figure>


<h3 id="13-3-C-代码实现"><a href="#13-3-C-代码实现" class="headerlink" title="13.3 C++ 代码实现"></a>13.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">FindNumbersWithSum</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; array,<span class="keyword">int</span> sum)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(array.<span class="built_in">empty</span>())<span class="keyword">return</span> array;</span><br><span class="line">        <span class="keyword">int</span> temp,flag=<span class="number">0</span>;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; target;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">0</span>;i&lt;array.<span class="built_in">size</span>()<span class="number">-1</span>;i++)&#123;</span><br><span class="line">            temp = sum-array[i];</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;array.<span class="built_in">size</span>();j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(temp == array[j])&#123;</span><br><span class="line">                    target.<span class="built_in">push_back</span>(array[i]);</span><br><span class="line">                    target.<span class="built_in">push_back</span>(array[j]);</span><br><span class="line">                    <span class="comment">//return target;</span></span><br><span class="line">                    flag =<span class="number">1</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(flag == <span class="number">1</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> target;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h2 id="14-和为S的连续正数序列"><a href="#14-和为S的连续正数序列" class="headerlink" title="14.和为S的连续正数序列"></a>14.和为S的连续正数序列</h2><h3 id="14-1-题目描述"><a href="#14-1-题目描述" class="headerlink" title="14.1 题目描述"></a>14.1 题目描述</h3><p>小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!</p>
<h3 id="14-2-输出描述"><a href="#14-2-输出描述" class="headerlink" title="14.2 输出描述:"></a>14.2 输出描述:</h3><p>输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序</p>
<h3 id="14-3-解题思路"><a href="#14-3-解题思路" class="headerlink" title="14.3 解题思路"></a>14.3 解题思路</h3><p>双指针移动，<br>当总和小于等于sum，大指针继续+<br>否则小指针+</p>
<h3 id="14-4-C-代码实现"><a href="#14-4-C-代码实现" class="headerlink" title="14.4 C++ 代码实现"></a>14.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    vector&lt;vector&lt;<span class="keyword">int</span>&gt; &gt; <span class="built_in">FindContinuousSequence</span>(<span class="keyword">int</span> sum) &#123;</span><br><span class="line">        vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt; target;</span><br><span class="line">        <span class="keyword">int</span> start=<span class="number">1</span>,end =<span class="number">2</span>;</span><br><span class="line">        <span class="keyword">int</span> temp_sum =<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(start&lt;end)&#123;</span><br><span class="line">            temp_sum = (end-start+<span class="number">1</span>)*(start+end)/<span class="number">2</span>;</span><br><span class="line">            <span class="keyword">if</span>(temp_sum&lt;sum)end++;</span><br><span class="line">            <span class="keyword">if</span>(temp_sum==sum)&#123;   </span><br><span class="line">                vector&lt;<span class="keyword">int</span>&gt;temp;</span><br><span class="line">                <span class="keyword">for</span>(<span class="keyword">int</span> i=start;i&lt;=end;i++)&#123;</span><br><span class="line">                    temp.<span class="built_in">push_back</span>(i);</span><br><span class="line">                &#125;</span><br><span class="line">                target.<span class="built_in">push_back</span>(temp);</span><br><span class="line">                start++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(temp_sum&gt;sum)start++;</span><br><span class="line">            </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> target;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="15-把字符串转成整数"><a href="#15-把字符串转成整数" class="headerlink" title="15.把字符串转成整数"></a>15.把字符串转成整数</h2><h3 id="15-1题目描述"><a href="#15-1题目描述" class="headerlink" title="15.1题目描述"></a>15.1题目描述</h3><p>将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0</p>
<p> <strong>输入描述:</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">输入一个字符串,包括数字字母符号,可以为空</span><br></pre></td></tr></table></figure>

<p> <strong>输出描述:</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">如果是合法的数值表达则返回该数字，否则返回0</span><br></pre></td></tr></table></figure>

<p>示例1</p>
<p> <strong>输入</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">+2147483647</span><br><span class="line">1a33</span><br></pre></td></tr></table></figure>

<p> <strong>输出</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">2147483647</span><br><span class="line">0</span><br></pre></td></tr></table></figure>
<h3 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h3><p>1.判断输入字符串长度，为0则，return 0；</p>
<p>2.去除字符串 符号前字符， while(str[i] ==’ ‘)i++;</p>
<p>3.判断是否有 +-号；</p>
<p>4.判断 数字是否 在0-9范围内</p>
<p>5.计算数字字符串转化为整数 number = number-str[i] -‘0’;</p>
<h3 id="C-代码实现"><a href="#C-代码实现" class="headerlink" title="C++ 代码实现"></a>C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">StrToInt</span><span class="params">(string str)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> sign =<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">long</span> <span class="keyword">long</span> number =<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span>(str.<span class="built_in">length</span>() &lt; <span class="number">1</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(str[i] ==<span class="string">&#x27; &#x27;</span>)i++;</span><br><span class="line">        <span class="keyword">if</span>(str[i] == <span class="string">&#x27;-&#x27;</span>)&#123;</span><br><span class="line">            i++;</span><br><span class="line">            sign = <span class="number">-1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(str[i] == <span class="string">&#x27;+&#x27;</span>)&#123;</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(str[i] != <span class="string">&#x27;\0&#x27;</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(str[i] &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; str[i]&lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">            &#123;</span><br><span class="line">               number = number*<span class="number">10</span>+str[i]-<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">               i++;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">             </span><br><span class="line">        &#125;</span><br><span class="line">        number *= sign;</span><br><span class="line">        <span class="keyword">return</span> number;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>


<h2 id="14-数组中出现超过一半的数字"><a href="#14-数组中出现超过一半的数字" class="headerlink" title="14.数组中出现超过一半的数字"></a>14.数组中出现超过一半的数字</h2><h3 id="14-1-题目描述-1"><a href="#14-1-题目描述-1" class="headerlink" title="14.1 题目描述"></a>14.1 题目描述</h3><p>请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。</p>
<h3 id="14-2-输出描述-1"><a href="#14-2-输出描述-1" class="headerlink" title="14.2 输出描述:"></a>14.2 输出描述:</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">如果当前字符流没有存在出现一次的字符，返回##字符。</span><br></pre></td></tr></table></figure>

<h3 id="14-3-题目翻译"><a href="#14-3-题目翻译" class="headerlink" title="14.3 题目翻译"></a><strong>14.3 题目翻译</strong></h3><p>计算第一个未重复的字符，</p>
<h3 id="14-4-解题思路"><a href="#14-4-解题思路" class="headerlink" title="14.4 解题思路"></a>14.4 解题思路</h3><p>用 map 进行匹配，vector进行遍历，。因map会自动排序，则不能单独使用map</p>
<p>map排序是按key值排序</p>
<p>unordered_map:排序 最后插入在最前面，先进后出。</p>
<h3 id="14-5-C-代码实现"><a href="#14-5-C-代码实现" class="headerlink" title="14.5 C++ 代码实现"></a>14.5 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">  <span class="comment">//Insert one char from stringstream</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Insert</span><span class="params">(<span class="keyword">char</span> ch)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="number">0</span> == mp[ch])temp.<span class="built_in">push_back</span>(ch);</span><br><span class="line">        mp[ch]++;</span><br><span class="line">    &#125;</span><br><span class="line">  <span class="comment">//return the first appearence once char in current stringstream</span></span><br><span class="line">    <span class="function"><span class="keyword">char</span> <span class="title">FirstAppearingOnce</span><span class="params">()</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">       <span class="keyword">for</span>(<span class="keyword">auto</span> val:temp)&#123;</span><br><span class="line">           <span class="keyword">if</span>(<span class="number">1</span>==mp[val])&#123;</span><br><span class="line">               <span class="keyword">return</span> val;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&#x27;#&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">     map&lt;<span class="keyword">char</span>,<span class="keyword">int</span>&gt; mp;</span><br><span class="line">    vector&lt;<span class="keyword">char</span>&gt; temp;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="15-左移旋转字符串"><a href="#15-左移旋转字符串" class="headerlink" title="15.左移旋转字符串"></a>15.左移旋转字符串</h2><h3 id="15-1-题目描述"><a href="#15-1-题目描述" class="headerlink" title="15.1 题目描述"></a>15.1 题目描述</h3><p>汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它</p>
<h3 id="15-2-题目翻译"><a href="#15-2-题目翻译" class="headerlink" title="15.2 题目翻译"></a>15.2 题目翻译</h3><p>环形字符串按位左移，</p>
<h3 id="15-3-解题思路"><a href="#15-3-解题思路" class="headerlink" title="15.3 解题思路"></a>15.3 解题思路</h3><p>1.截取字符串 左移的前几位</p>
<p>2.字符串左移</p>
<p>3.字符串添加</p>
<h3 id="15-4-C-代码实现"><a href="#15-4-C-代码实现" class="headerlink" title="15.4 C++ 代码实现"></a>15.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">string <span class="title">LeftRotateString</span><span class="params">(string str, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> i;</span><br><span class="line">        <span class="keyword">int</span> start =<span class="number">0</span>;</span><br><span class="line">        string temp = str.<span class="built_in">substr</span>(<span class="number">0</span>,n); <span class="comment">//字符串截取前n个</span></span><br><span class="line">        <span class="keyword">for</span>(i=n;i&lt;str.<span class="built_in">size</span>();i++)&#123;     <span class="comment">//字符串左移</span></span><br><span class="line">            str[start++]=str[i];  </span><br><span class="line">        &#125;</span><br><span class="line">         <span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;n;i++)&#123;             <span class="comment">//字符串添加</span></span><br><span class="line">             str[start++]=temp[i];   </span><br><span class="line">         &#125;  </span><br><span class="line">        <span class="keyword">return</span> str;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h2 id="16-平衡二叉树"><a href="#16-平衡二叉树" class="headerlink" title="16.平衡二叉树"></a>16.平衡二叉树</h2><h3 id="16-1-题目描述"><a href="#16-1-题目描述" class="headerlink" title="16.1 题目描述"></a>16.1 题目描述</h3><p>输入一棵二叉树，判断该二叉树是否是平衡二叉树。</p>
<p>在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树</p>
<h3 id="16-2-解题思路"><a href="#16-2-解题思路" class="headerlink" title="16.2 解题思路"></a>16.2 解题思路</h3><p>1.二叉树任意一节点左子节点的深度与左子节点的深度差小于等于1，为平衡二叉树</p>
<p>2.遍历数的深度，并判断任意子节点左右深度之差</p>
<h3 id="16-3-C-代码实现"><a href="#16-3-C-代码实现" class="headerlink" title="16.3 C++ 代码实现"></a>16.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">depth</span><span class="params">(TreeNode* pRoot)</span> <span class="comment">//数的深度</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(pRoot == <span class="literal">NULL</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> left = <span class="built_in">depth</span>(pRoot-&gt;left);</span><br><span class="line">        <span class="keyword">if</span>(left == <span class="number">-1</span>)<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">int</span> right = <span class="built_in">depth</span>(pRoot-&gt;right);</span><br><span class="line">        <span class="keyword">if</span>(right == <span class="number">-1</span>)<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">abs</span>(right-left)&gt;<span class="number">1</span>)<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>+(left&gt;right?left:right);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">IsBalanced_Solution</span><span class="params">(TreeNode* pRoot)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">return</span> <span class="built_in">depth</span>(pRoot) != <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">ret</span>&#123;</span></span><br><span class="line">         <span class="keyword">bool</span> judge;</span><br><span class="line">         <span class="keyword">int</span> value;</span><br><span class="line">    &#125;;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">maxdepth</span><span class="params">(TreeNode* pRoot,ret&amp; root)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        ret left,right;</span><br><span class="line">        <span class="keyword">if</span>(pRoot == <span class="literal">NULL</span>) &#123;</span><br><span class="line">           root.value=<span class="number">0</span>;</span><br><span class="line">           root.judge = <span class="literal">true</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        left.value = <span class="built_in">IsBalanced_Solution</span>(pRoot-&gt;left);</span><br><span class="line">        right.value = <span class="built_in">IsBalanced_Solution</span>(pRoot-&gt;right);</span><br><span class="line">        root.value =  <span class="number">1</span>+(left.value&gt;right.value?left.value:right.value);</span><br><span class="line">        root.judge = root.judge &amp;&amp; right.judge &amp;&amp; left.judge &amp;&amp; (<span class="built_in">abs</span>(left.value - right.value)&gt;<span class="number">1</span>?<span class="number">0</span>:<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">IsBalanced_Solution</span><span class="params">(TreeNode* pRoot)</span> </span>&#123;</span><br><span class="line">       ret result;</span><br><span class="line">       <span class="built_in">maxdepth</span>(pRoot,result);</span><br><span class="line">       <span class="keyword">return</span> result.judge;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="17-循环链表的入口节点"><a href="#17-循环链表的入口节点" class="headerlink" title="17.循环链表的入口节点"></a>17.循环链表的入口节点</h2><h3 id="17-1-题目描述"><a href="#17-1-题目描述" class="headerlink" title="17.1 题目描述"></a>17.1 题目描述</h3><p>给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。</p>
<h3 id="17-2-题目翻译"><a href="#17-2-题目翻译" class="headerlink" title="17.2 题目翻译"></a>17.2 <strong>题目翻译</strong></h3><p>一个尾部带环的链表，找到链表的结点</p>
<h3 id="17-3-解题思路"><a href="#17-3-解题思路" class="headerlink" title="17.3 解题思路"></a>17.3 解题思路</h3><p>使用 STL中的 set；</p>
<p>set的特点：set里面每个元素只存有一个key值，set容器自动对以上数据进行了排序，并且实现了去重。但是不能对set里的值进行修改。</p>
<p><strong>begin()   　　 返回set容器的第一个元素</strong><br><strong>end() 　　　 返回set容器的最后一个元素</strong><br><strong>clear()  　　   ,删除set容器中的所有的元素</strong><br><strong>empty() 　　　,判断set容器是否为空</strong><br><strong>max_size() 　 ,返回set容器可能包含的元素最大个数</strong><br><strong>size() 　　　　 ,返回当前set容器中的元素个数</strong><br><strong>rbegin　　　　 ,返回的值和end()相同</strong><br><strong>rend()　　　　 ,返回的值和rbegin()相同</strong><br><strong>count()         用来查找set中某个某个键值出现的次数</strong><br><strong>find() ，返回给定值的定位器，如果没找到则返回end()。</strong></p>
<h3 id="17-4-C-代码实现"><a href="#17-4-C-代码实现" class="headerlink" title="17.4 C++ 代码实现"></a>17.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">    int val;</span></span><br><span class="line"><span class="comment">    struct ListNode *next;</span></span><br><span class="line"><span class="comment">    ListNode(int x) :</span></span><br><span class="line"><span class="comment">        val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment">&#125;;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">EntryNodeOfLoop</span><span class="params">(ListNode* pHead)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">nullptr</span> == pHead)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        set&lt;ListNode *&gt; st;</span><br><span class="line">        ListNode* temp = pHead;</span><br><span class="line">        <span class="keyword">while</span>(temp != <span class="literal">nullptr</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(!st.<span class="built_in">count</span>(temp))&#123;<span class="comment">//如果 temp次数不为1； </span></span><br><span class="line">                st.<span class="built_in">insert</span>(temp);</span><br><span class="line">                temp=temp-&gt;next;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">    int val;</span></span><br><span class="line"><span class="comment">    struct ListNode *next;</span></span><br><span class="line"><span class="comment">    ListNode(int x) :</span></span><br><span class="line"><span class="comment">        val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment">&#125;;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">EntryNodeOfLoop</span><span class="params">(ListNode* pHead)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">nullptr</span> == pHead)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        set&lt;ListNode *&gt; st;</span><br><span class="line">        ListNode* temp = pHead;</span><br><span class="line">        <span class="keyword">while</span>(temp != <span class="literal">nullptr</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(st.<span class="built_in">find</span>(temp) == st.<span class="built_in">end</span>())&#123;</span><br><span class="line">                st.<span class="built_in">insert</span>(temp);</span><br><span class="line">                temp=temp-&gt;next;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="18-扑克牌顺子"><a href="#18-扑克牌顺子" class="headerlink" title="18.扑克牌顺子"></a>18.扑克牌顺子</h2><h3 id="18-1-题目描述"><a href="#18-1-题目描述" class="headerlink" title="18.1 题目描述"></a>18.1 题目描述</h3><p>LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。</p>
<h3 id="18-2-题目翻译"><a href="#18-2-题目翻译" class="headerlink" title="18.2 题目翻译"></a>18.2 题目翻译</h3><p>从输入的一个数组中判断能否构成5个一连的顺子，输入的数范围为0-13的整数，其中0可以表示1~13的任意整数。若能构成顺子，返回true，否则返回false</p>
<h3 id="18-3-解题思路"><a href="#18-3-解题思路" class="headerlink" title="18.3 解题思路"></a>18.3 解题思路</h3><p>1.判断数组长度，为空则，return false；</p>
<p>2.数组排序</p>
<p>3.计算大小王个数，并找到初值；</p>
<p>4.数组判断 </p>
<ul>
<li>无大小王，计算首尾差  </li>
<li>有大小王，判断大小王个数与首尾差</li>
</ul>
<h3 id="18-4-C-代码实现"><a href="#18-4-C-代码实现" class="headerlink" title="18.4 C++ 代码实现"></a>18.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">IsContinuous</span><span class="params">( vector&lt;<span class="keyword">int</span>&gt; numbers )</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> i =<span class="number">0</span>,num=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span>(numbers.<span class="built_in">empty</span>())<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="built_in">sort</span>(numbers.<span class="built_in">begin</span>(),numbers.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">for</span>(i;i&lt;numbers.<span class="built_in">size</span>();i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(<span class="number">0</span> == numbers[i])&#123;</span><br><span class="line">                num++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(<span class="number">0</span> == num)&#123;</span><br><span class="line">            <span class="keyword">if</span>(numbers.<span class="built_in">size</span>() == numbers.<span class="built_in">back</span>()-numbers[num]+<span class="number">1</span>)&#123;      <span class="comment">//无大小王，5连续</span></span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">            &#125;                                                          <span class="comment">// numbers.size()-num 非0数字的个数</span></span><br><span class="line">        &#125;                                                              <span class="comment">// numbers.back()-numbers[num]+1 首尾差</span></span><br><span class="line">        <span class="keyword">if</span>( numbers.<span class="built_in">back</span>()-numbers[num]+<span class="number">1</span>-(numbers.<span class="built_in">size</span>()-num)&lt;=num)&#123;  <span class="comment">// 有大小王，判断大小王个数，与首尾差之间的间隔</span></span><br><span class="line">            </span><br><span class="line">             <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>


<h2 id="19-数值的整数次方"><a href="#19-数值的整数次方" class="headerlink" title="19.数值的整数次方"></a>19.数值的整数次方</h2><h3 id="19-1-题目描述"><a href="#19-1-题目描述" class="headerlink" title="19.1 题目描述"></a>19.1 题目描述</h3><p>给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。</p>
<p>保证base和exponent不同时为0</p>
<h3 id="19-2-题目翻译"><a href="#19-2-题目翻译" class="headerlink" title="19.2 题目翻译"></a>19.2 题目翻译</h3><p>求数的整数次方</p>
<h3 id="19-3-解题思路"><a href="#19-3-解题思路" class="headerlink" title="19.3 解题思路"></a>19.3 解题思路</h3><p>连乘</p>
<h3 id="19-4-C-代码实现"><a href="#19-4-C-代码实现" class="headerlink" title="19.4 C++ 代码实现"></a>19.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">double</span> <span class="title">Power</span><span class="params">(<span class="keyword">double</span> base, <span class="keyword">int</span> exponent)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">double</span> res=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> n =<span class="built_in">abs</span>(exponent);</span><br><span class="line">        <span class="keyword">if</span>(n == <span class="number">0</span>)<span class="keyword">return</span> res;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            res*=base;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> (exponent &lt; <span class="number">0</span>)?<span class="number">1</span>/res:res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="20-数字在排序数组中出现的次数"><a href="#20-数字在排序数组中出现的次数" class="headerlink" title="20.数字在排序数组中出现的次数"></a>20.数字在排序数组中出现的次数</h2><h3 id="20-1-题目描述"><a href="#20-1-题目描述" class="headerlink" title="20.1 题目描述"></a>20.1 题目描述</h3><p>统计一个数字在排序数组中出现的次数。</p>
<h3 id="20-2-解题思路"><a href="#20-2-解题思路" class="headerlink" title="20.2 解题思路"></a>20.2 解题思路</h3><p>数组中查找目标数组</p>
<h3 id="20-3-C-代码实现"><a href="#20-3-C-代码实现" class="headerlink" title="20.3 C++ 代码实现"></a>20.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">GetNumberOfK</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; data ,<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;data.<span class="built_in">size</span>();i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(data[i] == k)n++;</span><br><span class="line">            <span class="keyword">if</span>(data[i]&gt;k)<span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> n;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">GetNumberOfK</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; nums ,<span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">upper_bound</span>(nums.<span class="built_in">begin</span>(), nums.<span class="built_in">end</span>(), target) - <span class="built_in">lower_bound</span>(nums.<span class="built_in">begin</span>(), nums.<span class="built_in">end</span>(), target);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="21-数组中出现超过一半的数字"><a href="#21-数组中出现超过一半的数字" class="headerlink" title="21.数组中出现超过一半的数字"></a>21.数组中出现超过一半的数字</h2><h3 id="21-1-题目描述"><a href="#21-1-题目描述" class="headerlink" title="21.1 题目描述"></a>21.1 题目描述</h3><p>如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。</p>
<h3 id="21-2-题目翻译"><a href="#21-2-题目翻译" class="headerlink" title="21.2 题目翻译"></a>21.2 <strong>题目翻译</strong></h3><p>计算当前插入数的中位数</p>
<h3 id="21-3-解题思路"><a href="#21-3-解题思路" class="headerlink" title="21.3 解题思路"></a>21.3 解题思路</h3><p>用 数组接受，然后用sort算法排序</p>
<h3 id="21-4-C-代码实现"><a href="#21-4-C-代码实现" class="headerlink" title="21.4 C++ 代码实现"></a>21.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">Insert</span><span class="params">(<span class="keyword">int</span> num)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        temp.<span class="built_in">push_back</span>(num);</span><br><span class="line">        <span class="built_in">sort</span>(temp.<span class="built_in">begin</span>(),temp.<span class="built_in">end</span>());</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">double</span> <span class="title">GetMedian</span><span class="params">()</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (temp.<span class="built_in">size</span>()&amp;<span class="number">1</span>)?temp[temp.<span class="built_in">size</span>()&gt;&gt;<span class="number">1</span>]:(temp[temp.<span class="built_in">size</span>()&gt;&gt;<span class="number">1</span>]+temp[(temp.<span class="built_in">size</span>()&gt;&gt;<span class="number">1</span>)<span class="number">-1</span>])/<span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    vector&lt;<span class="keyword">double</span>&gt;temp;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="22-数组中出现超过一半的数字"><a href="#22-数组中出现超过一半的数字" class="headerlink" title="22.数组中出现超过一半的数字"></a>22.数组中出现超过一半的数字</h2><h3 id="22-1-题目描述"><a href="#22-1-题目描述" class="headerlink" title="22.1 题目描述"></a>22.1 题目描述</h3><p>数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。</p>
<h3 id="22-2-题目翻译"><a href="#22-2-题目翻译" class="headerlink" title="22.2 题目翻译"></a>22.2 <strong>题目翻译</strong></h3><p>哈希 用map</p>
<h3 id="22-3-解题思路"><a href="#22-3-解题思路" class="headerlink" title="22.3 解题思路"></a>22.3 解题思路</h3><p>map 对应项自加</p>
<h3 id="22-4-C-代码实现"><a href="#22-4-C-代码实现" class="headerlink" title="22.4 C++ 代码实现"></a>22.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">MoreThanHalfNum_Solution</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; numbers)</span> </span>&#123;</span><br><span class="line">        map&lt;<span class="keyword">int</span>, <span class="keyword">int</span>&gt; mp;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">auto</span> value:numbers) ++mp[value];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">auto</span> val:numbers)&#123;</span><br><span class="line">            <span class="keyword">if</span>(mp[val]&gt;(numbers.<span class="built_in">size</span>()/<span class="number">2</span>))&#123;</span><br><span class="line">                <span class="keyword">return</span> val;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="23-和为S的连续正数序列"><a href="#23-和为S的连续正数序列" class="headerlink" title="23.和为S的连续正数序列"></a>23.和为S的连续正数序列</h2><h3 id="23-1-题目描述"><a href="#23-1-题目描述" class="headerlink" title="23.1 题目描述"></a>23.1 题目描述</h3><p>一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。</p>
<h3 id="23-2-解题思路"><a href="#23-2-解题思路" class="headerlink" title="23.2 解题思路"></a>23.2 解题思路</h3><p>1.从大到小排序</p>
<p>2.遍历一遍查找前后是否相同</p>
<h3 id="23-3-C-代码实现"><a href="#23-3-C-代码实现" class="headerlink" title="23.3 C++ 代码实现"></a>23.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">FindNumsAppearOnce</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; data,<span class="keyword">int</span>* num1,<span class="keyword">int</span> *num2)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> flag =<span class="number">0</span>;</span><br><span class="line">        <span class="built_in">sort</span>(data.<span class="built_in">begin</span>(),data.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">1</span>;i&lt;data.<span class="built_in">size</span>()<span class="number">-1</span>;i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(data[i] != data[i<span class="number">-1</span>]&amp;&amp; data[i]!= data[i+<span class="number">1</span>])&#123;</span><br><span class="line">                <span class="keyword">if</span>(flag ==<span class="number">1</span>)&#123;</span><br><span class="line">                    *num2 =data[i];</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                    *num1 =data[i];</span><br><span class="line">                    flag =<span class="number">1</span> ;  </span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(data[data.<span class="built_in">size</span>()<span class="number">-1</span>] != data[data.<span class="built_in">size</span>()<span class="number">-2</span>]) *num2 =data[data.<span class="built_in">size</span>()<span class="number">-1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="24-数组中的逆序对"><a href="#24-数组中的逆序对" class="headerlink" title="24.数组中的逆序对"></a>24.数组中的逆序对</h2><h3 id="24-1-题目描述"><a href="#24-1-题目描述" class="headerlink" title="24.1 题目描述"></a>24.1 题目描述</h3><p>在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007</p>
<h3 id="24-2-输入描述"><a href="#24-2-输入描述" class="headerlink" title="24.2 输入描述:"></a>24.2 输入描述:</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">题目保证输入的数组中没有的相同的数字数据范围：	对于%50的数据,size&lt;=10^4	对于%75的数据,size&lt;=10^5	对于%100的数据,size&lt;=2*10^5</span><br></pre></td></tr></table></figure>

<p>示例1</p>
<p><strong>输入</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">1,2,3,4,5,6,7,0</span><br></pre></td></tr></table></figure>

<p><strong>输出</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">7</span><br></pre></td></tr></table></figure>


<h3 id="24-3-C-代码实现"><a href="#24-3-C-代码实现" class="headerlink" title="24.3 C++ 代码实现"></a>24.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//插入排序法，算法复杂度过高，通过率为50%</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="keyword">const</span> <span class="keyword">int</span> kmod = <span class="number">1000000007</span>;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">InversePairs</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; data)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">int</span> num =<span class="number">0</span>;</span><br><span class="line">       <span class="keyword">if</span>(data.<span class="built_in">size</span>() == <span class="number">0</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;data.<span class="built_in">size</span>()<span class="number">-1</span>;i++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=i+<span class="number">1</span>;j&lt;data.<span class="built_in">size</span>();j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(data[i]&gt;data[j])&#123;</span><br><span class="line">                    num++;</span><br><span class="line">                    num%=kmod;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> num;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="25-数组中的重复数字"><a href="#25-数组中的重复数字" class="headerlink" title="25.数组中的重复数字"></a>25.数组中的重复数字</h2><h3 id="25-1-题目描述"><a href="#25-1-题目描述" class="headerlink" title="25.1 题目描述"></a>25.1 题目描述</h3><p>在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。</p>
<h3 id="25-2-解题思路及代码实现"><a href="#25-2-解题思路及代码实现" class="headerlink" title="25.2 解题思路及代码实现"></a>25.2 解题思路及代码实现</h3><ol>
<li><strong>遍历比较（时间复杂度：n²）</strong><br>因为要输出任意一个重复的数字，只要一个数字出现次数等于两次，就可以输出这个数了。可以选取第一个数作为基准，依次遍历这个数之后的所有数，如果有相等的数，就直接返回；如果没有，就选取第二个数作为基准，依次遍历第二个数后面的所有数，如果有相等的，就返回。</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">// Parameters:</span></span><br><span class="line">    <span class="comment">//        numbers:     an array of integers</span></span><br><span class="line">    <span class="comment">//        length:      the length of array numbers</span></span><br><span class="line">    <span class="comment">//        duplication: (Output) the duplicated number in the array number</span></span><br><span class="line">    <span class="comment">// Return value:       true if the input is valid, and there are some duplications in the array number</span></span><br><span class="line">    <span class="comment">//                     otherwise false</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">duplicate</span><span class="params">(<span class="keyword">int</span> numbers[], <span class="keyword">int</span> length, <span class="keyword">int</span>* duplication)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">0</span>;i&lt;length;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j =i+<span class="number">1</span>;j&lt;length;j++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(numbers[i] == numbers[j])</span><br><span class="line">                &#123;</span><br><span class="line">                    duplication[<span class="number">0</span>] = numbers[i];</span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<ol start="2">
<li><strong>hash思想 (空间复杂度高 )</strong></li>
</ol>
<p>开辟一个大小为n的数组Hash，遍历一遍用户输入的数组，将数组中的元素映射到HashTable数组中，比如：用户数组中有5，7，5，就分别将Hash中下标为5的位置+1，下标为7的位置+1，下标为5的位置再+1，直到遍历完成。那么每个数的出现次数都有了。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">// Parameters:</span></span><br><span class="line">    <span class="comment">//        numbers:     an array of integers</span></span><br><span class="line">    <span class="comment">//        length:      the length of array numbers</span></span><br><span class="line">    <span class="comment">//        duplication: (Output) the duplicated number in the array number</span></span><br><span class="line">    <span class="comment">// Return value:       true if the input is valid, and there are some duplications in the array number</span></span><br><span class="line">    <span class="comment">//                     otherwise false</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">duplicate</span><span class="params">(<span class="keyword">int</span> numbers[], <span class="keyword">int</span> length, <span class="keyword">int</span>* duplication)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> hash[<span class="number">1024</span>]=&#123;<span class="number">0</span>&#125;;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;length;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            ++hash[numbers[i]];</span><br><span class="line">            <span class="keyword">if</span>(hash[numbers[i]]&gt;<span class="number">1</span>)&#123;</span><br><span class="line">                duplication[<span class="number">0</span>] = numbers[i];</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<ol start="3">
<li><strong>数组排序（时间复杂度: n）</strong><br>首先给定数组arr[] = {2, 3, 0, 1, 3}。<br>因为数组中最大的数是n-1，那就一个萝卜一颗坑。<br>从0号下标位置开始，0号元素为2，不等于0，交换0号和2号位置，<br>数组变为：{0, 3, 2, 1, 3}。<br>再比较0号位置，下标和值相等，往后走到1号下标元素为3，不等于1，交换1号和3号，<br>变成：{0, 1, 2, 3, 3}。<br>再继续，下标来到4号位置，发现元素下标与值不相等，比较4号和3号下标位置，发现元素相等，返回3即可。</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">// Parameters:</span></span><br><span class="line">    <span class="comment">//        numbers:     an array of integers</span></span><br><span class="line">    <span class="comment">//        length:      the length of array numbers</span></span><br><span class="line">    <span class="comment">//        duplication: (Output) the duplicated number in the array number</span></span><br><span class="line">    <span class="comment">// Return value:       true if the input is valid, and there are some duplications in the array number</span></span><br><span class="line">    <span class="comment">//                     otherwise false</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">duplicate</span><span class="params">(<span class="keyword">int</span> numbers[], <span class="keyword">int</span> length, <span class="keyword">int</span>* duplication)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;length;i++)&#123;</span><br><span class="line">            <span class="keyword">while</span>(numbers[i] != i)&#123;</span><br><span class="line">                <span class="keyword">if</span>(numbers[i] == numbers[numbers[i]])&#123;</span><br><span class="line">                    duplication[<span class="number">0</span>] = numbers[i];</span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                    <span class="built_in">swap</span>(numbers[i],numbers[numbers[i]]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<h2 id="26-整数中1出现的次数"><a href="#26-整数中1出现的次数" class="headerlink" title="26.整数中1出现的次数"></a>26.整数中1出现的次数</h2><h3 id="26-1-题目描述"><a href="#26-1-题目描述" class="headerlink" title="26.1 题目描述"></a>26.1 题目描述</h3><p>求出1<del>13的整数中1出现的次数,并算出100</del>1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。</p>
<h3 id="26-2-题目翻译"><a href="#26-2-题目翻译" class="headerlink" title="26.2 题目翻译"></a>26.2 <strong>题目翻译</strong></h3><p>计算从1到n的数字中1出现的次数和</p>
<h3 id="26-3-解题思路"><a href="#26-3-解题思路" class="headerlink" title="26.3 解题思路"></a>26.3 解题思路</h3><p>从1到n进行遍历，每一个数计算从个位到最高位1的个数，因为是10进制，可以先从各位判断。再除以10</p>
<p>while(0!=n){</p>
<p>​    if(1 == n%10)count++;</p>
<p>​    n/=10;</p>
<p>}</p>
<h3 id="26-4-C-代码实现"><a href="#26-4-C-代码实现" class="headerlink" title="26.4 C++ 代码实现"></a>26.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">NumberOf1Between1AndN_Solution</span><span class="params">(<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> count =<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> temp =i;</span><br><span class="line">            <span class="keyword">while</span>(<span class="number">0</span> != temp)&#123;</span><br><span class="line">                <span class="keyword">if</span>(temp%<span class="number">10</span> == <span class="number">1</span>)count++;</span><br><span class="line">                temp /=<span class="number">10</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;;</span><br><span class="line">        <span class="keyword">return</span> count;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="27-旋转数组的最小值"><a href="#27-旋转数组的最小值" class="headerlink" title="27.旋转数组的最小值"></a>27.旋转数组的最小值</h2><h3 id="27-1-题目描述"><a href="#27-1-题目描述" class="headerlink" title="27.1 题目描述"></a>27.1 题目描述</h3><p>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。<br>NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。</p>
<h3 id="27-2-题目翻译"><a href="#27-2-题目翻译" class="headerlink" title="27.2 题目翻译"></a>27.2 <strong>题目翻译</strong></h3><p>递增数组旋转，查找最小</p>
<h3 id="27-3-解题思路"><a href="#27-3-解题思路" class="headerlink" title="27.3 解题思路"></a>27.3 解题思路</h3><p>两端同时查找，知道头和尾相同；</p>
<h3 id="27-4-C-代码实现"><a href="#27-4-C-代码实现" class="headerlink" title="27.4 C++ 代码实现"></a>27.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">minNumberInRotateArray</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; rotateArray)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (rotateArray.<span class="built_in">empty</span>())<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> i =<span class="number">0</span>,j=rotateArray.<span class="built_in">size</span>()<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">for</span>(i,j;i&lt;j;j--,i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(rotateArray[i] &gt; rotateArray[i+<span class="number">1</span>])<span class="keyword">return</span> rotateArray[i+<span class="number">1</span>];</span><br><span class="line">            <span class="keyword">if</span>(rotateArray[j<span class="number">-1</span>] &gt; rotateArray[j])<span class="keyword">return</span> rotateArray[j];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="28-最小的K个数"><a href="#28-最小的K个数" class="headerlink" title="28.最小的K个数"></a>28.最小的K个数</h2><h3 id="28-1-题目描述"><a href="#28-1-题目描述" class="headerlink" title="28.1 题目描述"></a>28.1 题目描述</h3><p>输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。</p>
<h3 id="28-2-题目翻译"><a href="#28-2-题目翻译" class="headerlink" title="28.2 题目翻译"></a>28.2 <strong>题目翻译</strong></h3><p>排序，提取前K个数</p>
<h3 id="28-3-解题思路"><a href="#28-3-解题思路" class="headerlink" title="28.3 解题思路"></a>28.3 解题思路</h3><p>排序，提取前K个数</p>
<h3 id="28-4-C-代码实现"><a href="#28-4-C-代码实现" class="headerlink" title="28.4 C++ 代码实现"></a>28.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">GetLeastNumbers_Solution</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; input, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">        <span class="keyword">if</span>(k==<span class="number">0</span>||k&gt;input.<span class="built_in">size</span>()) <span class="keyword">return</span> res;</span><br><span class="line">        <span class="built_in">sort</span>(input.<span class="built_in">begin</span>(),input.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">return</span> vector&lt;<span class="keyword">int</span>&gt;(&#123;input.<span class="built_in">begin</span>(),input.<span class="built_in">begin</span>()+k&#125;);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="29-栈的压入，弹出序列"><a href="#29-栈的压入，弹出序列" class="headerlink" title="29.栈的压入，弹出序列"></a>29.栈的压入，弹出序列</h2><h3 id="29-1-题目描述"><a href="#29-1-题目描述" class="headerlink" title="29.1 题目描述"></a>29.1 题目描述</h3><p>输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）</p>
<h3 id="29-2-题目翻译"><a href="#29-2-题目翻译" class="headerlink" title="29.2 题目翻译"></a>29.2 <strong>题目翻译</strong></h3><p>看看弹出序列是不是栈的弹出序列</p>
<h3 id="29-3-解题思路"><a href="#29-3-解题思路" class="headerlink" title="29.3 解题思路"></a>29.3 解题思路</h3><p>模仿栈的压入与弹出，看看最后栈是否为空</p>
<h3 id="29-4-C-代码实现"><a href="#29-4-C-代码实现" class="headerlink" title="29.4 C++ 代码实现"></a>29.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">IsPopOrder</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; pushV,vector&lt;<span class="keyword">int</span>&gt; popV)</span> </span>&#123;</span><br><span class="line">        stack&lt;<span class="keyword">int</span>&gt; st;</span><br><span class="line">        <span class="keyword">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (i &lt; pushV.<span class="built_in">size</span>()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (pushV[i] != popV[j]) &#123;</span><br><span class="line">                st.<span class="built_in">push</span>(pushV[i++]);</span><br><span class="line">            &#125;<span class="comment">//将压栈与出栈不相等的放入栈中。</span></span><br><span class="line">            <span class="keyword">else</span> &#123;<span class="comment">//相等了开始出栈</span></span><br><span class="line">                ++i, ++j;<span class="comment">//出栈下一个与栈顶比较</span></span><br><span class="line">                <span class="keyword">while</span> (!st.<span class="built_in">empty</span>() &amp;&amp; st.<span class="built_in">top</span>() == popV[j]) &#123;<span class="comment">//如果相等，出栈，直到不相等，及栈为空</span></span><br><span class="line">                    st.<span class="built_in">pop</span>();</span><br><span class="line">                    ++j;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="comment">// end outer while</span></span><br><span class="line">        <span class="keyword">return</span> st.<span class="built_in">empty</span>();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="30-求1-2-3-…-n"><a href="#30-求1-2-3-…-n" class="headerlink" title="30.求1+2+3+…+n"></a>30.求1+2+3+…+n</h2><h3 id="30-1-题目描述"><a href="#30-1-题目描述" class="headerlink" title="30.1 题目描述"></a>30.1 题目描述</h3><p>求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。</p>
<h3 id="30-2解题思路："><a href="#30-2解题思路：" class="headerlink" title="30.2解题思路："></a>30.2解题思路：</h3><p>求和公式<br>$$<br>sum= \frac{(1+n)*n}2<br>$$</p>
<h3 id="30-3-C-代码实现"><a href="#30-3-C-代码实现" class="headerlink" title="30.3 C++代码实现"></a>30.3 C++代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">Sum_Solution</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (n+<span class="number">1</span>)*n/<span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="31-二叉树的深度"><a href="#31-二叉树的深度" class="headerlink" title="31.二叉树的深度"></a>31.二叉树的深度</h2><h3 id="31-1题目描述"><a href="#31-1题目描述" class="headerlink" title="31. 1题目描述"></a>31. 1题目描述</h3><p>输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。</p>
<h3 id="31-2-解题思路"><a href="#31-2-解题思路" class="headerlink" title="31.2 解题思路"></a>31.2 解题思路</h3><p>依次递归遍历数的最大深度</p>
<h3 id="31-3-C-代码实现"><a href="#31-3-C-代码实现" class="headerlink" title="31.3 C++ 代码实现"></a>31.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct TreeNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct TreeNode *left;</span></span><br><span class="line"><span class="comment">	struct TreeNode *right;</span></span><br><span class="line"><span class="comment">	TreeNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), left(NULL), right(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">TreeDepth</span><span class="params">(TreeNode* pRoot)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">       <span class="keyword">if</span>(pRoot == <span class="literal">NULL</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">       <span class="keyword">int</span> left = <span class="built_in">TreeDepth</span>(pRoot-&gt;left);</span><br><span class="line">       <span class="keyword">int</span> right = <span class="built_in">TreeDepth</span>(pRoot-&gt;right);</span><br><span class="line">       <span class="keyword">return</span> <span class="built_in">max</span>(right,left)+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="32-把字符串转成整数"><a href="#32-把字符串转成整数" class="headerlink" title="32.把字符串转成整数"></a>32.把字符串转成整数</h2><h3 id="32-1-题目描述"><a href="#32-1-题目描述" class="headerlink" title="32.1 题目描述"></a>32.1 题目描述</h3><p>写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。</p>
<h3 id="32-2-解题思路"><a href="#32-2-解题思路" class="headerlink" title="32.2 解题思路"></a>32.2 解题思路</h3><p>数字电路中的全加器</p>
<table>
<thead>
<tr>
<th align="center">num1</th>
<th align="center">num2</th>
<th align="center">sum</th>
<th align="center">flag</th>
</tr>
</thead>
<tbody><tr>
<td align="center">0</td>
<td align="center">0</td>
<td align="center">0</td>
<td align="center">0</td>
</tr>
<tr>
<td align="center">0</td>
<td align="center">1</td>
<td align="center">1</td>
<td align="center">0</td>
</tr>
<tr>
<td align="center">1</td>
<td align="center">0</td>
<td align="center">1</td>
<td align="center">0</td>
</tr>
<tr>
<td align="center">1</td>
<td align="center">1</td>
<td align="center">0</td>
<td align="center">1</td>
</tr>
</tbody></table>
<p>sum=num1^num2</p>
<p>flag = (num1&amp;num2)&lt;&lt;1</p>
<h3 id="32-3-C-代码实现"><a href="#32-3-C-代码实现" class="headerlink" title="32.3 C++ 代码实现"></a>32.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">Add</span><span class="params">(<span class="keyword">int</span> num1, <span class="keyword">int</span> num2)</span></span></span><br><span class="line"><span class="function">    </span>&#123; <span class="comment">//全加器 画个真值表</span></span><br><span class="line">      <span class="comment">//进位 flag = (num1&amp;num2)&lt;1; </span></span><br><span class="line">      <span class="comment">//和 sum = num1^num2;</span></span><br><span class="line">      <span class="comment">//return num1 是为了防止 num2输入为0</span></span><br><span class="line"> #<span class="meta">#<span class="meta-keyword">if</span> 1</span></span><br><span class="line">      <span class="keyword">int</span> flag=<span class="number">0</span>;</span><br><span class="line">      <span class="keyword">int</span> sum =<span class="number">0</span>;</span><br><span class="line">      <span class="keyword">while</span>(num2!=<span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">          sum = num1^num2;</span><br><span class="line">          flag =(num1&amp;num2)&lt;&lt;<span class="number">1</span>;</span><br><span class="line">          num1 = sum;</span><br><span class="line">          num2 = flag;</span><br><span class="line">         &#125;</span><br><span class="line">         <span class="keyword">return</span> num1;</span><br><span class="line">#<span class="meta">#<span class="meta-keyword">else</span></span></span><br><span class="line">      <span class="comment">//第二种方法 </span></span><br><span class="line">      <span class="keyword">return</span> num2? <span class="built_in">Add</span>(num1^num2,(num1&amp;num2)&lt;&lt;<span class="number">1</span>):num1;</span><br><span class="line">#<span class="meta">#<span class="meta-keyword">endif</span></span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>


<h2 id="33-滑动窗口最大值"><a href="#33-滑动窗口最大值" class="headerlink" title="33.滑动窗口最大值"></a>33.滑动窗口最大值</h2><h3 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h3><p>给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。</p>
<p>窗口大于数组长度的时候，返回空</p>
<h3 id="33-1-题目翻译"><a href="#33-1-题目翻译" class="headerlink" title="33.1 题目翻译"></a>33.1 <strong>题目翻译</strong></h3><p>滑动窗口，</p>
<h3 id="33-2-解题思路"><a href="#33-2-解题思路" class="headerlink" title="33.2 解题思路"></a>33.2 解题思路</h3><p>使用双指针控制窗口大小，并移动</p>
<h3 id="33-3-C-代码实现"><a href="#33-3-C-代码实现" class="headerlink" title="33.3 C++ 代码实现"></a>33.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">maxInWindows</span><span class="params">(<span class="keyword">const</span> vector&lt;<span class="keyword">int</span>&gt;&amp; num, <span class="keyword">unsigned</span> <span class="keyword">int</span> size)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left =<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = size<span class="number">-1</span>;<span class="comment">//2</span></span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; ret;</span><br><span class="line">        <span class="keyword">if</span>(size &gt; num.<span class="built_in">size</span>() || size&lt;<span class="number">1</span> || num.<span class="built_in">size</span>() ==<span class="number">0</span>)<span class="keyword">return</span> ret;</span><br><span class="line">        <span class="keyword">while</span>(right&lt;num.<span class="built_in">size</span>())&#123;<span class="comment">//2&lt;8</span></span><br><span class="line">            <span class="keyword">int</span> index =left;<span class="comment">//0</span></span><br><span class="line">            <span class="keyword">int</span> temp=num[left];<span class="comment">//2</span></span><br><span class="line">            <span class="keyword">for</span>(index;index&lt;=right;index++)&#123;<span class="comment">//0;0&lt;=2;0++</span></span><br><span class="line">                temp = temp&gt;num[index]?temp:num[index];</span><br><span class="line">            &#125;</span><br><span class="line">            ret.<span class="built_in">push_back</span>(temp);</span><br><span class="line">            left++;<span class="comment">//0++</span></span><br><span class="line">            right++;<span class="comment">//2++</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ret;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="34-连续子数组的动态和"><a href="#34-连续子数组的动态和" class="headerlink" title="34.连续子数组的动态和"></a>34.连续子数组的动态和</h2><h3 id="34-1-题目描述"><a href="#34-1-题目描述" class="headerlink" title="34.1 题目描述"></a>34.1 题目描述</h3><p>我们可以用2<em>1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2</em>1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？</p>
<p>比如n=3时，2*3的矩形块有3种覆盖方法：</p>
<h3 id="34-2-题目翻译"><a href="#34-2-题目翻译" class="headerlink" title="34.2 题目翻译"></a>34.2 <strong>题目翻译</strong></h3><p>斐波那契数列</p>
<p>f(n)=f(n-1)+f(n-2);</p>
<p>.</p>
<p>f(2)=2</p>
<p>f(1)=1</p>
<h3 id="34-3-解题思路"><a href="#34-3-解题思路" class="headerlink" title="34.3 解题思路"></a>34.3 解题思路</h3><p>斐波那契数列</p>
<p>f(n)=f(n-1)+f(n-2);</p>
<p>.</p>
<p>f(2)=2</p>
<p>f(1)=1</p>
<h3 id="34-5-C-代码实现"><a href="#34-5-C-代码实现" class="headerlink" title="34.5 C++ 代码实现"></a>34.5 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">rectCover</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(number &lt;<span class="number">3</span>)<span class="keyword">return</span> number;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">rectCover</span>(number<span class="number">-1</span>)+<span class="built_in">rectCover</span>(number<span class="number">-2</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="35-替换空格"><a href="#35-替换空格" class="headerlink" title="35.替换空格"></a>35.替换空格</h2><h3 id="35-1-题目描述"><a href="#35-1-题目描述" class="headerlink" title="35.1 题目描述"></a>35.1 题目描述</h3><p>请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。</p>
<h3 id="35-2-题目翻译"><a href="#35-2-题目翻译" class="headerlink" title="35.2 题目翻译"></a>35.2 题目翻译</h3><p>把字符串中的空格替换为”%20“，原始字符串要加长。</p>
<h3 id="35-3-c-代码实现"><a href="#35-3-c-代码实现" class="headerlink" title="35.3 c++代码实现"></a>35.3 c++代码实现</h3><p><strong>思路一</strong></p>
<p>1.统计字符串中的空格的个数</p>
<p>2.从后往前进行替换</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">replaceSpace</span><span class="params">(<span class="keyword">char</span> *str,<span class="keyword">int</span> length)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;   </span><br><span class="line">        <span class="keyword">if</span>(length &lt; <span class="number">1</span>&amp;&amp;str == <span class="literal">NULL</span>)<span class="keyword">return</span>; </span><br><span class="line">        <span class="keyword">int</span> num=<span class="number">0</span>;<span class="comment">//空格个数</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;length;i++)&#123;</span><br><span class="line">             <span class="keyword">if</span>(<span class="string">&#x27; &#x27;</span> == str[i])num++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = length <span class="number">-1</span>;i&gt;=<span class="number">0</span>;i--)&#123;<span class="comment">//从后往前替换</span></span><br><span class="line">            <span class="keyword">if</span>(<span class="string">&#x27; &#x27;</span> != str[i])&#123;</span><br><span class="line">                str[i+<span class="number">2</span>*num]=str[i];</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                str[i+<span class="number">2</span>*num]=<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">                str[i+<span class="number">2</span>*num<span class="number">-1</span>]=<span class="string">&#x27;2&#x27;</span>;</span><br><span class="line">                str[i+<span class="number">2</span>*num<span class="number">-2</span>]=<span class="string">&#x27;%&#x27;</span>;</span><br><span class="line">                num--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p><strong>思路2</strong></p>
<p>1.将char * 转为 string;</p>
<p>2.用string.find()方法查找空格，</p>
<p>3.查找到插入%20</p>
<p>4.string 转为char *；</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">replaceSpace</span><span class="params">(<span class="keyword">char</span> *str,<span class="keyword">int</span> length)</span> </span>&#123;</span><br><span class="line">        <span class="function">string <span class="title">s</span><span class="params">(str)</span></span>;</span><br><span class="line">        <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>((i=s.<span class="built_in">find</span>(<span class="string">&#x27; &#x27;</span>,i))&gt;<span class="number">-1</span>)&#123;</span><br><span class="line">            s.<span class="built_in">erase</span>(i,<span class="number">1</span>);</span><br><span class="line">            s.<span class="built_in">insert</span>(i,<span class="string">&quot;%20&quot;</span>);</span><br><span class="line">             </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">auto</span> ret=s.<span class="built_in">c_str</span>();</span><br><span class="line">        <span class="built_in">strcpy</span>(str,ret);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="36-翻转单词顺序列"><a href="#36-翻转单词顺序列" class="headerlink" title="36.翻转单词顺序列"></a>36.翻转单词顺序列</h2><h3 id="36-1-题目描述"><a href="#36-1-题目描述" class="headerlink" title="36.1 题目描述"></a>36.1 题目描述</h3><p>牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？</p>
<h3 id="36-2-题目翻译"><a href="#36-2-题目翻译" class="headerlink" title="36.2 题目翻译"></a>36.2 题目翻译</h3><p>将字符串数组反转，然后，以空格为单位间隔性翻转</p>
<h3 id="36-3-解题思路"><a href="#36-3-解题思路" class="headerlink" title="36.3 解题思路"></a>36.3 解题思路</h3><p>1.数组整体翻转</p>
<p>2.以空格为分界，单词翻转</p>
<h3 id="36-4-C-代码实现"><a href="#36-4-C-代码实现" class="headerlink" title="36.4 C++ 代码实现"></a>36.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">string <span class="title">ReverseSentence</span><span class="params">(string str)</span> </span>&#123;</span><br><span class="line">        <span class="built_in">reverse</span>(str.<span class="built_in">begin</span>(),str.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">int</span> start=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i =<span class="number">0</span>;i&lt;str.<span class="built_in">size</span>();i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(str[i] == <span class="string">&#x27; &#x27;</span>)&#123;</span><br><span class="line">                <span class="built_in">reverse</span>(str.<span class="built_in">begin</span>()+start,str.<span class="built_in">begin</span>()+i);</span><br><span class="line">                start=i+<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(i+<span class="number">1</span> == str.<span class="built_in">size</span>())&#123;</span><br><span class="line">                <span class="built_in">reverse</span>(str.<span class="built_in">begin</span>()+start,str.<span class="built_in">end</span>());</span><br><span class="line">            &#125;   </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> str;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>附录</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">string <span class="title">reverse</span><span class="params">(<span class="keyword">char</span> * begin;<span class="keyword">char</span> * end)</span></span></span><br><span class="line"><span class="function"></span>&#123;	</span><br><span class="line">    <span class="keyword">while</span>(begin != end)</span><br><span class="line">        <span class="built_in">swap</span>(begin ++;end--);</span><br><span class="line">    </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="37-调整数组奇数位于偶数前面"><a href="#37-调整数组奇数位于偶数前面" class="headerlink" title="37.调整数组奇数位于偶数前面"></a>37.调整数组奇数位于偶数前面</h2><h3 id="37-1-题目描述"><a href="#37-1-题目描述" class="headerlink" title="37.1 题目描述"></a>37.1 题目描述</h3><p>输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。</p>
<h3 id="37-2-题目翻译"><a href="#37-2-题目翻译" class="headerlink" title="37.2 题目翻译"></a>37.2 <strong>题目翻译</strong></h3><p>数组处理</p>
<h3 id="37-3-解题思路"><a href="#37-3-解题思路" class="headerlink" title="37.3 解题思路"></a>37.3 解题思路</h3><h3 id="37-4-C-代码实现"><a href="#37-4-C-代码实现" class="headerlink" title="37.4 C++ 代码实现"></a>37.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">reOrderArray</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; &amp;array)</span> </span>&#123;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; ood ;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; event;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">auto</span> value:array)(value%<span class="number">2</span>)?event.<span class="built_in">push_back</span>(value):ood.<span class="built_in">push_back</span>(value);</span><br><span class="line">        array.<span class="built_in">erase</span>(array.<span class="built_in">begin</span>(),array.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">auto</span> value:event)array.<span class="built_in">push_back</span>(value);</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">auto</span> value:ood)array.<span class="built_in">push_back</span>(value);</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="38-进制中1的个数"><a href="#38-进制中1的个数" class="headerlink" title="38.进制中1的个数"></a>38.进制中1的个数</h2><h3 id="38-1-题目描述"><a href="#38-1-题目描述" class="headerlink" title="38.1 题目描述"></a>38.1 题目描述</h3><p>输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。</p>
<h3 id="38-2-题目翻译"><a href="#38-2-题目翻译" class="headerlink" title="38.2 题目翻译"></a>38.2 <strong>题目翻译</strong></h3><p>位移运算</p>
<h3 id="38-3-C-代码实现"><a href="#38-3-C-代码实现" class="headerlink" title="38.3 C++ 代码实现"></a>38.3 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">     <span class="function"><span class="keyword">int</span>  <span class="title">NumberOf1</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> mark = <span class="number">0x01</span>;</span><br><span class="line">        <span class="keyword">while</span> (mark != <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (mark &amp; val) ++ans;</span><br><span class="line">            mark &lt;&lt;= <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">         <span class="keyword">return</span> ans;</span><br><span class="line">     &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="39-连续子数组的动态和"><a href="#39-连续子数组的动态和" class="headerlink" title="39.连续子数组的动态和"></a>39.连续子数组的动态和</h2><h3 id="39-1-题目描述"><a href="#39-1-题目描述" class="headerlink" title="39.1 题目描述"></a>39.1 题目描述</h3><p>HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)</p>
<h3 id="39-2-题目翻译"><a href="#39-2-题目翻译" class="headerlink" title="39.2 题目翻译"></a>39.2 <strong>题目翻译</strong></h3><p>求最大连续子数组的动态和，数组需要为连续的，不定长度的</p>
<h3 id="39-3-解题思路"><a href="#39-3-解题思路" class="headerlink" title="39.3 解题思路"></a>39.3 解题思路</h3><p>用二维数组模拟，i，j表示从i到j个元素的和，求最大。</p>
<h3 id="39-4-C-代码实现"><a href="#39-4-C-代码实现" class="headerlink" title="39.4 C++ 代码实现"></a>39.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">FindGreatestSumOfSubArray</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; array)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = array.<span class="built_in">size</span>();</span><br><span class="line">        <span class="keyword">if</span>(len&lt;<span class="number">1</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt;<span class="built_in">res</span>(len, vector&lt;<span class="keyword">int</span>&gt;(len));<span class="comment">//n x n的二维数组</span></span><br><span class="line">        <span class="keyword">int</span> max;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len;i++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j =i;j&lt;len;j++)&#123; <span class="comment">//j=i目的是只取右上三角。</span></span><br><span class="line">                <span class="keyword">int</span> temp =i;</span><br><span class="line">                <span class="keyword">if</span>(temp != j)&#123;</span><br><span class="line">                    <span class="keyword">while</span>(temp&lt;=j)&#123;</span><br><span class="line">                        res[i][j]+=array[temp];</span><br><span class="line">                        temp++;</span><br><span class="line">                        <span class="keyword">if</span>(j &gt; <span class="number">0</span>)&#123;</span><br><span class="line">                        max = (res[i][j]&lt;max?max:res[i][j]);</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                    res[i][j]=array[i];</span><br><span class="line">                    <span class="keyword">if</span>(j==<span class="number">0</span>)&#123;</span><br><span class="line">                        max =res[i][j];</span><br><span class="line">                    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(j &gt; <span class="number">0</span>)&#123;</span><br><span class="line">                        max = (res[i][j]&lt;max?max:res[i][j]);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> max;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="40-重建二叉树"><a href="#40-重建二叉树" class="headerlink" title="40.重建二叉树"></a>40.重建二叉树</h2><h3 id="40-1-题目描述"><a href="#40-1-题目描述" class="headerlink" title="40.1 题目描述"></a>40.1 题目描述</h3><p>输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。</p>
<h3 id="40-2-题目翻译"><a href="#40-2-题目翻译" class="headerlink" title="40.2 题目翻译"></a>40.2 <strong>题目翻译</strong></h3><p>根据前序遍历和，中序遍历求二叉树。</p>
<h3 id="40-3-解题思路"><a href="#40-3-解题思路" class="headerlink" title="40.3 解题思路"></a>40.3 解题思路</h3><p>递归，</p>
<p>前序：根左右。中序：左根右。后续：左右根。</p>
<h3 id="40-4-C-代码实现"><a href="#40-4-C-代码实现" class="headerlink" title="40.4 C++ 代码实现"></a>40.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for binary tree</span></span><br><span class="line"><span class="comment"> * struct TreeNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     TreeNode *left;</span></span><br><span class="line"><span class="comment"> *     TreeNode *right;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x) : val(x), left(NULL), right(NULL) &#123;&#125;</span></span><br><span class="line"><span class="comment"> * &#125;;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">rebuild</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt;&amp; pre,<span class="keyword">int</span> pl,<span class="keyword">int</span> pr,vector&lt;<span class="keyword">int</span>&gt;&amp; vin,<span class="keyword">int</span> vl,<span class="keyword">int</span> vr)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(pl&gt;pr)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">int</span> mid;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vin.<span class="built_in">size</span>();i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(vin[i] == pre[pl])&#123;</span><br><span class="line">                mid = i;        <span class="comment">//根节点在中序中的位置</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        TreeNode * root = <span class="keyword">new</span> <span class="built_in">TreeNode</span>(pre[pl]);</span><br><span class="line">        root-&gt;left=<span class="built_in">rebuild</span>(pre,pl+<span class="number">1</span>,pl+mid-vl,vin,vl,mid<span class="number">-1</span>);<span class="comment">//pl+mid-vl 左子树起始点</span></span><br><span class="line">        root-&gt;right=<span class="built_in">rebuild</span>(pre,pl+mid-vl+<span class="number">1</span>,pr,vin,mid+<span class="number">1</span>,vr);<span class="comment">//pl+mid-vl+1 右子树起始点</span></span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function">TreeNode* <span class="title">reConstructBinaryTree</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; pre,vector&lt;<span class="keyword">int</span>&gt; vin)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">rebuild</span>(pre,<span class="number">0</span>,pre.<span class="built_in">size</span>()<span class="number">-1</span>,vin,<span class="number">0</span>,vin.<span class="built_in">size</span>()<span class="number">-1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="41-链表中倒数第K个节点"><a href="#41-链表中倒数第K个节点" class="headerlink" title="41.链表中倒数第K个节点"></a>41.链表中倒数第K个节点</h2><h3 id="41-1-题目描述"><a href="#41-1-题目描述" class="headerlink" title="41. 1 题目描述"></a>41. 1 题目描述</h3><p>输入一个链表，输出该链表中倒数第k个结点。</p>
<h3 id="41-2-题目翻译"><a href="#41-2-题目翻译" class="headerlink" title="41.2 题目翻译"></a>41.2 <strong>题目翻译</strong></h3><p>输出指定节点</p>
<h3 id="41-3-解题思路"><a href="#41-3-解题思路" class="headerlink" title="41.3 解题思路"></a>41.3 解题思路</h3><p>1.遍历链表，存入数组</p>
<p>2.返回倒数第K个节点</p>
<blockquote>
<p>注意：</p>
<p>​    1.链表长度为空</p>
<p>​    2.指定位置大于链表长度</p>
</blockquote>
<h3 id="41-4-C-代码实现"><a href="#41-4-C-代码实现" class="headerlink" title="41.4 C++ 代码实现"></a>41.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct ListNode *next;</span></span><br><span class="line"><span class="comment">	ListNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">FindKthToTail</span><span class="params">(ListNode* pListHead, <span class="keyword">unsigned</span> <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> == pListHead||k &lt; <span class="number">1</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;<span class="comment">//链表为空，指定位置小于0</span></span><br><span class="line">        vector&lt;ListNode*&gt; arr;</span><br><span class="line">        <span class="keyword">int</span> len =<span class="number">0</span>; <span class="comment">//计算链表个数</span></span><br><span class="line">        ListNode* temp = pListHead;</span><br><span class="line">        <span class="keyword">while</span>(<span class="literal">NULL</span> != temp)&#123;</span><br><span class="line">            arr.<span class="built_in">push_back</span>(temp);</span><br><span class="line">            ++len;<span class="comment">//记录数组一共多少个元素</span></span><br><span class="line">            temp = temp-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(len&lt;k)<span class="keyword">return</span> <span class="literal">nullptr</span>;<span class="comment">//指定位置大于数组长度</span></span><br><span class="line">        <span class="keyword">return</span> arr[len-k]; <span class="comment">//数组序号从0开始，所以用len-k</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="42-反转链表"><a href="#42-反转链表" class="headerlink" title="42.反转链表"></a>42.反转链表</h2><h3 id="42-1-题目描述"><a href="#42-1-题目描述" class="headerlink" title="42.1 题目描述"></a>42.1 题目描述</h3><p>输入一个链表，反转链表后，输出新链表的表头。</p>
<h3 id="42-2-题目翻译"><a href="#42-2-题目翻译" class="headerlink" title="42.2 题目翻译"></a>42.2 题目翻译</h3><p>链表反转3种思路</p>
<p>一，挨个遍历，进行反转</p>
<p>二，用栈stack，入栈出栈进行反转。（注意：第一个入栈的需要将next指向 NULL）</p>
<p>三，递归思路</p>
<h3 id="42-3-解题思路"><a href="#42-3-解题思路" class="headerlink" title="42.3 解题思路"></a>42.3 解题思路</h3><p>思路一</p>
<p>​    遍历链表，进行替换</p>
<h3 id="42-4-C-代码实现"><a href="#42-4-C-代码实现" class="headerlink" title="42.4 C++ 代码实现"></a>42.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">struct ListNode &#123;</span></span><br><span class="line"><span class="comment">	int val;</span></span><br><span class="line"><span class="comment">	struct ListNode *next;</span></span><br><span class="line"><span class="comment">	ListNode(int x) :</span></span><br><span class="line"><span class="comment">			val(x), next(NULL) &#123;</span></span><br><span class="line"><span class="comment">	&#125;</span></span><br><span class="line"><span class="comment">&#125;;*/</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">ListNode* <span class="title">ReverseList</span><span class="params">(ListNode* pHead)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="literal">NULL</span> == pHead &amp;&amp; <span class="literal">NULL</span> == pHead-&gt;next)<span class="keyword">return</span> pHead;</span><br><span class="line">        ListNode * pre  = <span class="literal">nullptr</span>;</span><br><span class="line">        ListNode * cur  = pHead;</span><br><span class="line">        ListNode * next = <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">while</span>(<span class="literal">NULL</span> != cur)&#123;</span><br><span class="line">            next=cur-&gt;next;</span><br><span class="line">            cur-&gt;next=pre;</span><br><span class="line">            pre=cur;</span><br><span class="line">            cur=next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> pre;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="43-顺时针打印矩阵"><a href="#43-顺时针打印矩阵" class="headerlink" title="43.顺时针打印矩阵"></a>43.顺时针打印矩阵</h2><h3 id="43-1-题目描述"><a href="#43-1-题目描述" class="headerlink" title="43.1 题目描述"></a>43.1 题目描述</h3><p>输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.</p>
<h3 id="43-2-题目翻译"><a href="#43-2-题目翻译" class="headerlink" title="43.2 题目翻译"></a>43.2 题目翻译</h3><p>按照 左-右 ，上-下，右-左，下-上 打印矩阵</p>
<h3 id="43-3-解题思路"><a href="#43-3-解题思路" class="headerlink" title="43.3 解题思路"></a>43.3 解题思路</h3><p>四个方向按顺序开始打印，左等于右，且上等于下，停止打印</p>
<h3 id="43-4-C-代码实现"><a href="#43-4-C-代码实现" class="headerlink" title="43.4 C++ 代码实现"></a>43.4 C++ 代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">printMatrix</span><span class="params">(vector&lt;vector&lt;<span class="keyword">int</span>&gt; &gt; matrix)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> row = matrix.<span class="built_in">size</span>();    <span class="comment">//行数</span></span><br><span class="line">        <span class="keyword">int</span> col = matrix[<span class="number">0</span>].<span class="built_in">size</span>(); <span class="comment">//列数</span></span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; res;</span><br><span class="line">        <span class="keyword">if</span>(row &lt; <span class="number">1</span> || col &lt; <span class="number">1</span>)<span class="keyword">return</span> res;</span><br><span class="line">        <span class="keyword">int</span> left=<span class="number">0</span>,right=col<span class="number">-1</span>,top=<span class="number">0</span>,bottom=row<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">while</span>(left &lt;= right &amp;&amp; top &lt;=bottom )&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i =left;i&lt;=right;i++)res.<span class="built_in">push_back</span>(matrix[top][i]);<span class="comment">//左-右打印</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i =top+<span class="number">1</span>;i&lt;=bottom;i++)res.<span class="built_in">push_back</span>(matrix[i][right]);<span class="comment">//上-下</span></span><br><span class="line">            <span class="keyword">if</span>(top!=bottom)<span class="keyword">for</span>(<span class="keyword">int</span> i =right<span class="number">-1</span>;i&gt;=left;i--)res.<span class="built_in">push_back</span>(matrix[bottom][i]);<span class="comment">//右-左</span></span><br><span class="line">            <span class="keyword">if</span>(left != right)<span class="keyword">for</span>(<span class="keyword">int</span> i =bottom<span class="number">-1</span>;i&gt;top;i--)res.<span class="built_in">push_back</span>(matrix[i][left]);<span class="comment">//下-上 </span></span><br><span class="line">            left++;top++;right--;bottom--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h2 id="44-已知后序和中序，求树"><a href="#44-已知后序和中序，求树" class="headerlink" title="44 已知后序和中序，求树"></a>44 已知后序和中序，求树</h2><h3 id="44-1-c-代码实现"><a href="#44-1-c-代码实现" class="headerlink" title="44.1 c++代码实现"></a>44.1 c++代码实现</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for binary tree</span></span><br><span class="line"><span class="comment"> * struct TreeNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     TreeNode *left;</span></span><br><span class="line"><span class="comment"> *     TreeNode *right;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x) : val(x), left(NULL), right(NULL) &#123;&#125;</span></span><br><span class="line"><span class="comment"> * &#125;;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function">TreeNode* <span class="title">rebuild</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt;&amp; pre,<span class="keyword">int</span> pl,<span class="keyword">int</span> pr,vector&lt;<span class="keyword">int</span>&gt;&amp; vin,<span class="keyword">int</span> vl,<span class="keyword">int</span> vr)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(pl&gt;pr)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">        <span class="keyword">int</span> mid;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;vin.<span class="built_in">size</span>();i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(vin[i] == pre[pl])&#123;</span><br><span class="line">                mid = i;        <span class="comment">//根节点在中序中的位置</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        TreeNode * root = <span class="keyword">new</span> <span class="built_in">TreeNode</span>(pre[pl]);</span><br><span class="line">        root-&gt;left=<span class="built_in">rebuild</span>(pre,pl+<span class="number">1</span>,pl+mid-vl,vin,vl,mid<span class="number">-1</span>);<span class="comment">//pl+mid-vl 左子树起始点</span></span><br><span class="line">        root-&gt;right=<span class="built_in">rebuild</span>(pre,pl+mid-vl+<span class="number">1</span>,pr,vin,mid+<span class="number">1</span>,vr);<span class="comment">//pl+mid-vl+1 右子树起始点</span></span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function">TreeNode* <span class="title">reConstructBinaryTree</span><span class="params">(vector&lt;<span class="keyword">int</span>&gt; pre,vector&lt;<span class="keyword">int</span>&gt; vin)</span> </span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">rebuild</span>(pre,<span class="number">0</span>,pre.<span class="built_in">size</span>()<span class="number">-1</span>,vin,<span class="number">0</span>,vin.<span class="built_in">size</span>()<span class="number">-1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>


    </div>

    
    
    
	<div>
		
			<div>
	
		<div style="text-align:center;color: #ccc;font-size:16px;">---------------------------------------本文结束<i class="fa fa-paw"></i>感谢您的阅读---------------------------------------</div>
	
</div>
		
	</div>
	<div>
		
			
<div class="my_post_copyright">
<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
<!-- JS库 sweetalert 可修改路径 -->
<script src="https://cdn.bootcss.com/jquery/2.0.0/jquery.min.js"></script>
<script src="https://unpkg.com/sweetalert/dist/sweetalert.min.js"></script>
<p><span>本文标题:</span><a href="/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/">剑指offer算法练习</a></p>
<!--
<p><span>文章作者:</span><a href="/" title="访问  的个人博客"></a></p>
-->
<p><span>发布时间:</span>2020年10月04日 - 21:02</p>
<p><span>最后更新:</span>2021年08月22日 - 11:17</p>
<p><span>原始链接:</span><a href="/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/" title="剑指offer算法练习">https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/</a>
<span class="copy-path" title="点击复制文章链接"><i class="fa fa-clipboard" data-clipboard-text="https://hyw-zero.github.io/2020/10/05/%E5%89%91%E6%8C%87offer%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/" aria-label="复制成功！"></i></span>
</p>
<p><span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">署名-非商业性使用-禁止演绎 4.0 国际</a> 转载请保留原文链接及作者。</p>
</div>
<script>
var clipboard = new Clipboard('.fa-clipboard');
$(".fa-clipboard").click(function(){
clipboard.on('success', function(){
swal({
title: "",
text: '复制成功',
icon: "success",
showConfirmButton: true
});
});
});
</script>

		
	</div>

    <footer class="post-footer">
          <div class="reward-container">
  <div></div>
  <button>
    赞赏
  </button>
  <div class="post-reward">
      <div>
        <img src="/images/wx.png" alt="hyw-zero 微信">
        <span>微信</span>
      </div>
      <div>
        <img src="/images/alipay.png" alt="hyw-zero 支付宝">
        <span>支付宝</span>
      </div>

  </div>
</div>

          <div class="post-tags">
              <a href="/tags/C/" rel="tag"><i class="fa fa-tag"></i>C++</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2019/05/01/linux%E8%BF%9B%E7%A8%8B%E9%80%9A%E4%BF%A1-%E5%85%B1%E4%BA%AB%E5%86%85%E5%AD%98/" rel="prev" title="Linux进程通信(共享内存)">
                  <i class="fa fa-chevron-left"></i> Linux进程通信(共享内存)
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2021/02/06/%E5%8D%81%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/" rel="next" title="十大排序算法">
                  十大排序算法 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="lv-container" data-id="city" data-uid="MTAyMC80MzU4NC8yMDEyMw=="></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">hyw-zero</span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
<div class="theme-info">
	<i class="fa fa-edit" style="font-size:18px"></i>
	<span class="post-count">博客全站共98.2k字</span>
</div>
    </div>
  </footer>

  
  <script src="https://cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script>

  
<script src="/js/third-party/search/local-search.js"></script>



  <script class="next-config" data-name="nprogress" type="application/json">{"enable":true,"spinner":true}</script>
  <script src="/js/third-party/nprogress.js"></script>

  
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>




<script src="/js/third-party/comments/livere.js"></script>
</body>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/love.js"></script>
</html>

